Scippy

SCIP

Solving Constraint Integer Programs

cons_setppc.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file cons_setppc.c
26  * @ingroup DEFPLUGINS_CONS
27  * @brief Constraint handler for the set partitioning / packing / covering constraints \f$1^T x\ \{=, \le, \ge\}\ 1\f$.
28  * @author Tobias Achterberg
29  * @author Michael Winkler
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include "blockmemshell/memory.h"
35 #include "scip/cons_nonlinear.h"
36 #include "scip/cons_linear.h"
37 #include "scip/cons_setppc.h"
38 #include "scip/pub_conflict.h"
39 #include "scip/pub_cons.h"
40 #include "scip/pub_event.h"
41 #include "scip/pub_lp.h"
42 #include "scip/pub_message.h"
43 #include "scip/pub_misc.h"
44 #include "scip/pub_misc_sort.h"
45 #include "scip/pub_var.h"
46 #include "scip/scip_conflict.h"
47 #include "scip/scip_cons.h"
48 #include "scip/scip_cut.h"
49 #include "scip/scip_event.h"
50 #include "scip/scip_general.h"
51 #include "scip/scip_lp.h"
52 #include "scip/scip_mem.h"
53 #include "scip/scip_message.h"
54 #include "scip/scip_nlp.h"
55 #include "scip/scip_numerics.h"
56 #include "scip/scip_param.h"
57 #include "scip/scip_prob.h"
58 #include "scip/scip_probing.h"
59 #include "scip/scip_randnumgen.h"
60 #include "scip/scip_sol.h"
61 #include "scip/scip_solvingstats.h"
62 #include "scip/scip_var.h"
63 #include "scip/symmetry_graph.h"
65 #include <string.h>
66 
67 
68 #define CONSHDLR_NAME "setppc"
69 #define CONSHDLR_DESC "set partitioning / packing / covering constraints"
70 #define CONSHDLR_SEPAPRIORITY +700000 /**< priority of the constraint handler for separation */
71 #define CONSHDLR_ENFOPRIORITY -700000 /**< priority of the constraint handler for constraint enforcing */
72 #define CONSHDLR_CHECKPRIORITY -700000 /**< priority of the constraint handler for checking feasibility */
73 #define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
74 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
75 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
76  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
77 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
78 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
79 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
80 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
81 
82 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
83 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
84 
85 #define LINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of linear constraints */
86 #define NONLINCONSUPGD_PRIORITY +700000 /**< priority of the constraint handler for upgrading of nonlinear constraints */
87 
88 #define EVENTHDLR_NAME "setppc"
89 #define EVENTHDLR_DESC "bound change event handler for set partitioning / packing / covering constraints"
90 
91 #define CONFLICTHDLR_NAME "setppc"
92 #define CONFLICTHDLR_DESC "conflict handler creating set covering constraints"
93 #define CONFLICTHDLR_PRIORITY LINCONSUPGD_PRIORITY
94 
95 #define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
96 
97 #define HASHSIZE_SETPPCCONS 500 /**< minimal size of hash table in setppc constraint tables */
98 #define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
99 #define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
100 #define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
102 #define DEFAULT_RANDSEED 3
104 /*#define VARUSES*/ /* activate variable usage counting, that is necessary for LP and pseudo branching */
105 /*#define BRANCHLP*/ /* BRANCHLP is only useful if the ENFOPRIORITY is set to a positive value */
106 #ifdef BRANCHLP
107 #define MINBRANCHWEIGHT 0.3 /**< minimum weight of both sets in binary set branching */
108 #define MAXBRANCHWEIGHT 0.7 /**< maximum weight of both sets in binary set branching */
109 #endif
110 #define DEFAULT_NPSEUDOBRANCHES 2 /**< number of children created in pseudo branching (0: disable branching) */
111 #define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving steps be performed? */
113 #define DEFAULT_CLIQUELIFTING FALSE /**< should we try to lift variables into other clique constraints, fix
114  * variables, aggregate them, and also shrink the amount of variables in
115  * clique constraints
116  */
117 #define DEFAULT_ADDVARIABLESASCLIQUES FALSE/**< should we try to generate extra clique constraint out of all binary
118  * variables to hopefully fasten the detection of redundant clique
119  * constraints */
120 #define DEFAULT_CLIQUESHRINKING TRUE /**< should we try to shrink the number of variables in a clique constraints, by
121  * replacing more than one variable by only one
122  */
123 
124 /* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
125 
126 /*
127  * Data structures
128  */
129 
130 /** constraint handler data */
131 struct SCIP_ConshdlrData
132 {
133  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
134  SCIP_CONSHDLR* conshdlrlinear; /**< pointer to linear constraint handler or NULL if not included */
135 #ifdef VARUSES
136  SCIP_INTARRAY* varuses; /**< number of times a var is used in the active setppc constraints */
137 #endif
138  SCIP_Longint nsetpart; /**< number of set partitioning constraints in transformed problem */
139  int npseudobranches; /**< number of children created in pseudo branching (0 to disable branching) */
140  int noldfixedvars; /**< number of fixed variables after last clique lifting run */
141  int noldimpls; /**< number of implication before last clique lifting run */
142  int noldcliques; /**< number of cliques before last clique lifting run */
143  int noldupgrs; /**< number of setppc constraints since the last clique lifting run */
144  int nclqpresolve; /**< number of setppc clique lifting runs */
145  SCIP_Bool updatedsetppctype; /**< remember whether we upgraded a constraint type */
146  SCIP_Bool cliquelifting; /**< should we perform the clique lifting procedure */
147  SCIP_Bool enablecliquelifting;/**< check whether we have enough changes to run the lifting procedure again */
148  SCIP_Bool cliqueshrinking; /**< should we try to shrink the number of variables in a clique
149  * constraints, by replacing more than one variable by only one
150  */
151  SCIP_Bool addvariablesascliques;/**< should we try to generate extra clique constraint out of all binary
152  * variables to hopefully fasten the detection of redundant clique
153  * constraints */
154  SCIP_RANDNUMGEN* randnumgen; /**< random number generator */
155  SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
156  SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
157  SCIP_Bool dualpresolving; /**< should dual presolving steps be performed? */
158 };
159 
160 /** constraint data for set partitioning / packing / covering constraints */
161 struct SCIP_ConsData
162 {
163  uint64_t signature; /**< bit signature of vars array */
164  SCIP_ROW* row; /**< LP row, if constraint is already stored in LP row format */
165  SCIP_NLROW* nlrow; /**< NLP row, if constraint has been added to NLP relaxation */
166  SCIP_VAR** vars; /**< variables of the constraint */
167  int varssize; /**< size of vars array */
168  int nvars; /**< number of variables in the constraint */
169  int nfixedzeros; /**< current number of variables fixed to zero in the constraint */
170  int nfixedones; /**< current number of variables fixed to one in the constraint */
171  unsigned int setppctype:2; /**< type of constraint: set partitioning, packing or covering */
172  unsigned int sorted:1; /**< are the constraint's variables sorted? */
173  unsigned int cliqueadded:1; /**< was the set partitioning / packing constraint already added as clique? */
174  unsigned int validsignature:1; /**< is the bit signature valid? */
175  unsigned int changed:1; /**< was constraint changed since last redundancy round in preprocessing? */
176  unsigned int varsdeleted:1; /**< were variables deleted after last cleanup? */
177  unsigned int merged:1; /**< are the constraint's equal/negated variables already merged? */
178  unsigned int presolpropagated:1; /**< was the constraint already propagated in presolving w.r.t. the current domains? */
179  unsigned int existmultaggr:1; /**< does this constraint contain aggregations */
180  unsigned int catchevents:1; /**< are events installed for this constraint? */
181 };
182 
183 
184 
185 
186 /*
187  * Local methods
188  */
189 
190 /** compares two active constraints of type set partitioning or set packing such that a "-1" is return if
191  * 1. the first constraint is a set partitioning constraint and the second is a set packing or
192  * 2. both constraints are set partitioning constraints and the second has more! variables than the first or
193  * 3. both constraints are set packing constraints and the second has less! variables than the first
194  * a "0" is return if
195  * 1. both constraint are of the same type and have the amount of variables or
196  * and a "1" is returned otherwise
197  */
198 static
199 int setppcCompare(
200  SCIP_CONS*const cons1, /**< first problem variable */
201  SCIP_CONS*const cons2 /**< second problem variable */
202  )
203 {
204  SCIP_CONSDATA* consdata1;
205  SCIP_CONSDATA* consdata2;
206 
207  assert(cons1 != NULL);
208  assert(cons2 != NULL);
209  assert(SCIPconsIsActive(cons1));
210  assert(SCIPconsIsActive(cons2));
211 
212  /* the partitioning type should be the smallest value and the packing the second smallest */
213  assert(SCIP_SETPPCTYPE_PARTITIONING < SCIP_SETPPCTYPE_PACKING); /*lint !e506*/
214 
215  consdata1 = SCIPconsGetData(cons1);
216  assert(consdata1 != NULL);
217  assert(consdata1->setppctype != SCIP_SETPPCTYPE_COVERING); /*lint !e641*/
218  consdata2 = SCIPconsGetData(cons2);
219  assert(consdata2 != NULL);
220  assert(consdata2->setppctype != SCIP_SETPPCTYPE_COVERING); /*lint !e641*/
221 
222  if( consdata1->setppctype < consdata2->setppctype ||
223  (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) || /*lint !e641*/
224  (consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars) ) /*lint !e641*/
225  return -1;
226  else if( (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars) ) /*lint !e641*/
227  return 0;
228  else
229  {
230  assert(consdata1->setppctype > consdata2->setppctype || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars > consdata2->nvars) || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->setppctype == consdata2->setppctype && consdata1->nvars < consdata2->nvars)); /*lint !e641*/
231  return +1;
232  }
233 }
234 
235 /** sort constraints first after type (partitioning before packing before covering) and second after number of
236  * variables such that the partitioning constraints have increasing number of variables and the packing constraints
237  * have decreasing number of variables */
238 static
239 SCIP_DECL_SORTPTRCOMP(setppcConssSort)
240 {
241  return setppcCompare((SCIP_CONS*)elem1, (SCIP_CONS*)elem2);
242 }
243 
244 /** compares two setppc constraints such that a "-1" is return if the first constraint is active and
245  * 1. the second constraint is deleted
246  * 2. the first constraint is a set partitioning constraint and the second is a set packing or
247  * 3. both constraints are set partitioning constraints and the second has more! variables than the first or
248  * 4. both constraints are set packing constraints and the second has less! variables than the first
249  * a "0" is return if
250  * 1. both constraint are set-covering constraints
251  * 2. both constraint are of the same type and have the amount of variables or
252  * and a "1" is returned otherwise
253  */
254 static
255 int setppcCompare2(
256  SCIP_CONS*const cons1, /**< first problem variable */
257  SCIP_CONS*const cons2 /**< second problem variable */
258  )
259 {
260  SCIP_CONSDATA* consdata1;
261  SCIP_CONSDATA* consdata2;
262 
263  assert(cons1 != NULL);
264  assert(cons2 != NULL);
265 
266  if( SCIPconsIsDeleted(cons1) )
267  {
268  if( SCIPconsIsDeleted(cons2) )
269  return 0;
270  else
271  return +1;
272  }
273  else if( SCIPconsIsDeleted(cons2) )
274  return -1;
275 
276  consdata1 = SCIPconsGetData(cons1);
277  assert(consdata1 != NULL);
278  consdata2 = SCIPconsGetData(cons2);
279  assert(consdata2 != NULL);
280 
281  /* the partitioning type should be the smallest value and the packing the second smallest */
283 
284  if( consdata1->setppctype < consdata2->setppctype ||
285  ((SCIP_SETPPCTYPE)consdata1->setppctype != SCIP_SETPPCTYPE_COVERING &&
286  (((SCIP_SETPPCTYPE)consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars < consdata2->nvars) ||
287  ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars > consdata2->nvars))) )
288  return -1;
289  else if( ((SCIP_SETPPCTYPE)consdata2->setppctype == SCIP_SETPPCTYPE_COVERING || (consdata1->setppctype == consdata2->setppctype && consdata1->nvars == consdata2->nvars)) )
290  return 0;
291  else
292  {
293  assert(consdata1->setppctype > consdata2->setppctype || ((consdata1->setppctype == consdata2->setppctype) &&
294  ((consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nvars > consdata2->nvars)
295  || (consdata1->setppctype == SCIP_SETPPCTYPE_PACKING && consdata1->nvars < consdata2->nvars)))); /*lint !e641*/
296  return +1;
297  }
298 }
299 
300 /** sort constraints first after type (partitioning before packing before covering) and second after number of
301  * variables such that the partitioning constraints have increasing number of variables and the packing constraints
302  * have decreasing number of variables */
303 static
304 SCIP_DECL_SORTPTRCOMP(setppcConssSort2)
305 {
306  return setppcCompare2((SCIP_CONS*)elem1, (SCIP_CONS*)elem2);
307 }
308 
309 
310 /** installs rounding locks for the given variable in the given setppc constraint */
311 static
313  SCIP* scip, /**< SCIP data structure */
314  SCIP_CONS* cons, /**< setppc constraint */
315  SCIP_VAR* var /**< variable of constraint entry */
316  )
317 {
318  SCIP_CONSDATA* consdata;
319 
320  consdata = SCIPconsGetData(cons);
321  assert(consdata != NULL);
322 
323  switch( consdata->setppctype )
324  {
326  SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
327  break;
329  SCIP_CALL( SCIPlockVarCons(scip, var, cons, FALSE, TRUE) );
330  break;
332  SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, FALSE) );
333  break;
334  default:
335  SCIPerrorMessage("unknown setppc type\n");
336  return SCIP_INVALIDDATA;
337  }
338 
339  return SCIP_OKAY;
340 }
341 
342 /** removes rounding locks for the given variable in the given setppc constraint */
343 static
345  SCIP* scip, /**< SCIP data structure */
346  SCIP_CONS* cons, /**< setppc constraint */
347  SCIP_VAR* var /**< variable of constraint entry */
348  )
349 {
350  SCIP_CONSDATA* consdata;
351 
352  consdata = SCIPconsGetData(cons);
353  assert(consdata != NULL);
354 
355  switch( consdata->setppctype )
356  {
358  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
359  break;
361  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, FALSE, TRUE) );
362  break;
364  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, FALSE) );
365  break;
366  default:
367  SCIPerrorMessage("unknown setppc type\n");
368  return SCIP_INVALIDDATA;
369  }
370 
371  return SCIP_OKAY;
372 }
373 
374 /** creates constraint handler data for set partitioning / packing / covering constraint handler */
375 static
377  SCIP* scip, /**< SCIP data structure */
378  SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
379  SCIP_EVENTHDLR* eventhdlr /**< event handler */
380  )
381 {
382  assert(scip != NULL);
383  assert(conshdlrdata != NULL);
384  assert(eventhdlr != NULL);
385 
386  SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
387 #ifdef VARUSES
388  SCIP_CALL( SCIPcreateIntarray(scip, &(*conshdlrdata)->varuses) );
389 #endif
390  (*conshdlrdata)->npseudobranches = DEFAULT_NPSEUDOBRANCHES;
391 
392  /* set event handler for bound change events */
393  (*conshdlrdata)->eventhdlr = eventhdlr;
394  (*conshdlrdata)->nsetpart = 0;
395 
396  /* create a random number generator */
397  SCIP_CALL( SCIPcreateRandom(scip, &(*conshdlrdata)->randnumgen,
399 
400  return SCIP_OKAY;
401 }
402 
403 /** frees constraint handler data for set partitioning / packing / covering constraint handler */
404 static
406  SCIP* scip, /**< SCIP data structure */
407  SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
408  )
409 {
410  assert(conshdlrdata != NULL);
411  assert(*conshdlrdata != NULL);
412 
413 #ifdef VARUSES
414  SCIP_CALL( SCIPfreeIntarray(scip, &(*conshdlrdata)->varuses) );
415 #endif
416 
417  /* free random number generator */
418  SCIPfreeRandom(scip, &(*conshdlrdata)->randnumgen);
419 
420  SCIPfreeBlockMemory(scip, conshdlrdata);
421 
422  return SCIP_OKAY;
423 }
424 
425 #ifdef VARUSES
426 /** adds the given value to the usage counter of the given variable */
427 static
428 SCIP_RETCODE conshdlrdataAddVaruses(
429  SCIP* scip, /**< SCIP data structure */
430  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
431  SCIP_VAR* var, /**< variable to increase usage counter for */
432  int addval /**< value to add to the usage counter */
433  )
434 {
435  SCIP_INTARRAY* varuses;
436 
437  assert(conshdlrdata != NULL);
438  assert(var != NULL);
439 
440  varuses = conshdlrdata->varuses;
441  assert(varuses != NULL);
442 
443  /* if the variable is the negation of a problem variable, count the varuses in the problem variable */
444  if( SCIPvarIsNegated(var) )
445  {
446  SCIP_VAR* negvar;
447  int varindex;
448 
449  /* move the varuses value of the negated variable to the active problem variable */
450  varindex = SCIPvarGetIndex(var);
451  addval += SCIPgetIntarrayVal(scip, varuses, varindex);
452  SCIP_CALL( SCIPsetIntarrayVal(scip, varuses, varindex, 0) );
453  SCIP_CALL( SCIPgetNegatedVar(scip, var, &negvar) );
454  var = negvar;
455  }
456 
457  /* increase varuses counter */
458  SCIP_CALL( SCIPincIntarrayVal(scip, varuses, SCIPvarGetIndex(var), addval) );
459 
460  SCIPdebugMsg(scip, "added %d to varuses of <%s>: %d\n",
461  addval, SCIPvarGetName(var), SCIPgetIntarrayVal(scip, varuses, SCIPvarGetIndex(var)));
462 
463  return SCIP_OKAY;
464 }
465 
466 /** increases the usage counter of the given variable */
467 static
468 SCIP_RETCODE conshdlrdataIncVaruses(
469  SCIP* scip, /**< SCIP data structure */
470  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
471  SCIP_VAR* var /**< variable to increase usage counter for */
472  )
473 {
474  assert(conshdlrdata != NULL);
475 
476  SCIPdebugMsg(scip, "increasing varuses of <%s>: %d\n",
477  SCIPvarGetName(var), SCIPgetIntarrayVal(scip, conshdlrdata->varuses, SCIPvarGetIndex(var)));
478 
479  SCIP_CALL( conshdlrdataAddVaruses(scip, conshdlrdata, var, +1) );
480 
481  return SCIP_OKAY;
482 }
483 
484 /** decreases the usage counter of the given variable */
485 static
486 SCIP_RETCODE conshdlrdataDecVaruses(
487  SCIP* scip, /**< SCIP data structure */
488  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
489  SCIP_VAR* var /**< variable to increase usage counter for */
490  )
491 {
492  assert(conshdlrdata != NULL);
493 
494  SCIPdebugMsg(scip, "decreasing varuses of <%s>: %d\n",
495  SCIPvarGetName(var), SCIPgetIntarrayVal(scip, conshdlrdata->varuses, SCIPvarGetIndex(var)));
496 
497  SCIP_CALL( conshdlrdataAddVaruses(scip, conshdlrdata, var, -1) );
498 
499  return SCIP_OKAY;
500 }
501 
502 /** increases the usage counter of all variable in the constraint */
503 static
504 SCIP_RETCODE consdataIncVaruses(
505  SCIP* scip, /**< SCIP data structure */
506  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
507  SCIP_CONSDATA* consdata /**< setppc constraint data */
508  )
509 {
510  int v;
511 
512  assert(consdata != NULL);
513 
514  for( v = 0; v < consdata->nvars; ++v )
515  {
516  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, consdata->vars[v]) );
517  }
518 
519  return SCIP_OKAY;
520 }
521 
522 /** decreases the usage counter of all variable in the constraint */
523 static
524 SCIP_RETCODE consdataDecVaruses(
525  SCIP* scip, /**< SCIP data structure */
526  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
527  SCIP_CONSDATA* consdata /**< setppc constraint data */
528  )
529 {
530  int v;
531 
532  assert(consdata != NULL);
533 
534  for( v = 0; v < consdata->nvars; ++v )
535  {
536  SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, consdata->vars[v]) );
537  }
538 
539  return SCIP_OKAY;
540 }
541 #endif
542 
543 /** ensures, that the vars array can store at least num entries */
544 static
546  SCIP* scip, /**< SCIP data structure */
547  SCIP_CONSDATA* consdata, /**< setppc constraint data */
548  int num /**< minimum number of entries to store */
549  )
550 {
551  assert(consdata != NULL);
552  assert(consdata->nvars <= consdata->varssize);
554  if( num > consdata->varssize )
555  {
556  int newsize;
557 
558  newsize = SCIPcalcMemGrowSize(scip, num);
559  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
560  consdata->varssize = newsize;
561  }
562  assert(num <= consdata->varssize);
563 
564  return SCIP_OKAY;
565 }
566 
567 /** creates a set partitioning / packing / covering constraint data object */
568 static
570  SCIP* scip, /**< SCIP data structure */
571  SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
572  int nvars, /**< number of variables in the constraint */
573  SCIP_VAR** vars, /**< variables of the constraint */
574  SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
575  )
576 {
577  assert(consdata != NULL);
578  assert(nvars == 0 || vars != NULL);
579 
580  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
581 
582  (*consdata)->signature = 0;
583  (*consdata)->row = NULL;
584  (*consdata)->nlrow = NULL;
585  (*consdata)->existmultaggr = FALSE;
586  (*consdata)->catchevents = FALSE;
587  (*consdata)->nfixedzeros = 0;
588  (*consdata)->nfixedones = 0;
589 
590  if( nvars > 0 )
591  {
592  int v;
593 
594  /* @todo the setppc constraint handler does not remove fixed variables from its var array; removing those
595  * variables is only possible if we consider the values of nfixedones and nfixedzeros in all propagation methods
596  */
597 #ifdef SCIP_DISABLED_CODE
598 
599  if( SCIPisConsCompressionEnabled(scip) )
600  {
601  SCIP_VAR** varsbuffer;
602  int k;
603 
604  /* allocate temporary buffer storage for active variables */
605  SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
606 
607  k = 0;
608  /* collect fixed variables to compress the required memory */
609  for( v = 0; v < nvars; ++v )
610  {
611  assert(SCIPvarIsBinary(vars[v]));
612 
613  /* already fixed variables account as fixed ones or zero, only unfixed are appended */
614  if( SCIPvarGetLbGlobal(vars[v]) > 0.5 )
615  (*consdata)->nfixedones++;
616  else if( SCIPvarGetUbGlobal(vars[v]) < 0.5 )
617  (*consdata)->nfixedzeros++;
618  else
619  varsbuffer[k++] = vars[v];
620  }
621 
622  (*consdata)->varssize = k;
623  (*consdata)->nvars = k;
624  /* copy unfixed variables into constraint data */
625  if( k > 0 )
626  {
627  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
628  }
629 
630  /* free temporary storage */
631  SCIPfreeBufferArray(scip, &varsbuffer);
632  }
633  else
634 #endif
635  {
636  /* for uncompressed copies, simply duplicate the whole array */
637  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
638  (*consdata)->varssize = nvars;
639  (*consdata)->nvars = nvars;
640  }
641 
642  if( SCIPisTransformed(scip) )
643  {
644  /* get transformed variables */
645  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
646 
647  /* check for multi-aggregations and capture variables */
648  for( v = 0; v < (*consdata)->nvars; v++ )
649  {
650  SCIP_VAR* var = SCIPvarGetProbvar((*consdata)->vars[v]);
651  assert(var != NULL);
652  (*consdata)->existmultaggr = (*consdata)->existmultaggr || (SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
653  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
654  }
655  }
656  else
657  {
658  /* capture variables */
659  for( v = 0; v < (*consdata)->nvars; v++ )
660  {
661  assert((*consdata)->vars[v] != NULL);
662  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
663  }
664  }
665  }
666  else
667  {
668  (*consdata)->vars = NULL;
669  (*consdata)->varssize = 0;
670  (*consdata)->nvars = 0;
671  }
672  (*consdata)->setppctype = setppctype; /*lint !e641*/
673  (*consdata)->sorted = (nvars <= 1);
674  (*consdata)->cliqueadded = FALSE;
675  (*consdata)->validsignature = FALSE;
676  (*consdata)->changed = TRUE;
677  (*consdata)->varsdeleted = FALSE;
678  (*consdata)->merged = FALSE;
679  (*consdata)->presolpropagated = FALSE;
680 
681  return SCIP_OKAY;
682 }
683 
684 /** creates a transformed set partitioning / packing / covering constraint data object */
685 static
687  SCIP* scip, /**< SCIP data structure */
688  SCIP_CONSDATA** consdata, /**< pointer to store the set partitioning / packing / covering constraint */
689  int nvars, /**< number of variables in the constraint */
690  SCIP_VAR** vars, /**< variables of the constraint */
691  SCIP_SETPPCTYPE setppctype /**< type of constraint: set partitioning, packing, or covering constraint */
692  )
693 {
694  assert(consdata != NULL);
695  assert(nvars == 0 || vars != NULL);
696 
697  /* create constraint data */
698  SCIP_CALL( consdataCreate(scip, consdata, nvars, vars, setppctype) );
699 
700  /* transform the variables */
701  SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
702 
703  return SCIP_OKAY;
704 }
705 
706 /** frees a set partitioning / packing / covering constraint data */
707 static
709  SCIP* scip, /**< SCIP data structure */
710  SCIP_CONSDATA** consdata /**< pointer to store the set partitioning / packing / covering constraint */
711  )
712 {
713  int v;
714 
715  assert(consdata != NULL);
716  assert(*consdata != NULL);
717 
718  /* release the row */
719  if( (*consdata)->row != NULL )
720  {
721  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row) );
722  }
723 
724  /* release the nlrow */
725  if( (*consdata)->nlrow != NULL )
726  {
727  SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow) );
728  }
729 
730  /* release variables */
731  for( v = 0; v < (*consdata)->nvars; v++ )
732  {
733  assert((*consdata)->vars[v] != NULL);
734  SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
735  }
736 
737  SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
738  SCIPfreeBlockMemory(scip, consdata);
739 
740  return SCIP_OKAY;
741 }
742 
743 /** prints set partitioning / packing / covering constraint to file stream */
744 static
746  SCIP* scip, /**< SCIP data structure */
747  SCIP_CONSDATA* consdata, /**< set partitioning / packing / covering constraint data */
748  FILE* file /**< output file (or NULL for standard output) */
749  )
750 {
751  assert(consdata != NULL);
752 
753  /* print coefficients */
754  if( consdata->nvars == 0 )
755  SCIPinfoMessage(scip, file, "0 ");
756 
757  /* write linear sum */
758  SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, consdata->vars, NULL, consdata->nvars, TRUE) );
759 
760  /* print right hand side */
761  switch( consdata->setppctype )
762  {
764  SCIPinfoMessage(scip, file, " == 1");
765  break;
767  SCIPinfoMessage(scip, file, " <= 1");
768  break;
770  SCIPinfoMessage(scip, file, " >= 1");
771  break;
772  default:
773  SCIPerrorMessage("unknown setppc type\n");
774  return SCIP_ERROR;
775  }
776 
777  return SCIP_OKAY;
778 }
779 
780 /** returns the bit signature of the given constraint data */
781 static
782 uint64_t consdataGetSignature(
783  SCIP_CONSDATA* consdata /**< set partitioning / packing / covering constraint data */
784  )
785 {
786  assert(consdata != NULL);
787 
788  if( !consdata->validsignature )
789  {
790  int i;
791 
792  consdata->signature = 0;
793  for( i = 0; i < consdata->nvars; ++i )
794  consdata->signature |= SCIPhashSignature64(SCIPvarGetIndex(consdata->vars[i]));
795  consdata->validsignature = TRUE;
796  }
797 
798  return consdata->signature;
799 }
800 
801 /** sorts setppc constraint's variables by non-decreasing variable index */
802 static
803 void consdataSort(
804  SCIP_CONSDATA* consdata /**< linear constraint data */
805  )
806 {
807  assert(consdata != NULL);
808 
809  if( !consdata->sorted )
810  {
811  if( consdata->nvars <= 1 )
812  consdata->sorted = TRUE;
813  else
814  {
815  SCIPsortPtr((void**)consdata->vars, SCIPvarComp, consdata->nvars);
816  consdata->sorted = TRUE;
817  }
818  }
819  assert(consdata->sorted);
820 #ifdef SCIP_DEBUG
821  /* check sorting */
822  {
823  int v;
824 
825  for( v = 0; v < consdata->nvars; ++v )
826  {
827  assert(v == consdata->nvars-1 || SCIPvarCompare(consdata->vars[v], consdata->vars[v+1]) <= 0);
828  }
829  }
830 #endif
831 }
832 
833 /** changes the type of a setppc constraint */
834 static
836  SCIP* scip, /**< SCIP data structure */
837  SCIP_CONS* cons, /**< setppc constraint */
838  SCIP_SETPPCTYPE setppctype /**< new type of constraint */
839  )
840 {
841  SCIP_CONSHDLR* conshdlr;
842  SCIP_CONSHDLRDATA* conshdlrdata;
843  SCIP_CONSDATA* consdata;
844  SCIP_Bool locked;
845  int i;
846 
847  consdata = SCIPconsGetData(cons);
848  assert(consdata != NULL);
849 
850  if( (SCIP_SETPPCTYPE)consdata->setppctype == setppctype )
851  return SCIP_OKAY;
852 
853  SCIPdebugMsg(scip, " -> converting <%s> into setppc type %d\n", SCIPconsGetName(cons), setppctype);
854 
855  /* remove rounding locks */
856  locked = FALSE;
857  for( i = 0; i < NLOCKTYPES && !locked; i++ )
858  locked = SCIPconsIsLockedType(cons, (SCIP_LOCKTYPE) i);
859 
860  if( locked )
861  {
862  for( i = 0; i < consdata->nvars; ++i )
863  {
864  SCIP_CALL( unlockRounding(scip, cons, consdata->vars[i]) );
865  }
866  }
867 
868  conshdlr = SCIPconsGetHdlr(cons);
869  assert(conshdlr != NULL);
870  conshdlrdata = SCIPconshdlrGetData(conshdlr);
871  assert(conshdlrdata != NULL);
872 
873  if( SCIPisTransformed(scip) )
874  {
875  if( setppctype == SCIP_SETPPCTYPE_PARTITIONING )
876  {
877  ++(conshdlrdata->nsetpart);
878  assert(conshdlrdata->nsetpart >= 0);
879  }
880  else if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
881  {
882  --(conshdlrdata->nsetpart);
883  assert(conshdlrdata->nsetpart >= 0);
884  }
885  }
886 
887  /* change the constraint type */
888  consdata->setppctype = setppctype; /*lint !e641*/
889 
890  /* reinstall rounding locks again */
891  if( locked )
892  {
893  for( i = 0; i < consdata->nvars; ++i )
894  {
895  SCIP_CALL( lockRounding(scip, cons, consdata->vars[i]) );
896  }
897  }
898 
899  /* remember that we changed a constraint type for clique lifting procedure */
900  if( setppctype != SCIP_SETPPCTYPE_COVERING )
901  conshdlrdata->updatedsetppctype = TRUE;
902 
903  return SCIP_OKAY;
904 }
905 
906 /** catches events for variable at given position */
907 static
909  SCIP* scip, /**< SCIP data structure */
910  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
911  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
912  int pos /**< array position of variable to catch bound change events for */
913  )
914 {
915  SCIP_CONSDATA* consdata;
916  SCIP_EVENTTYPE eventtype;
917  SCIP_VAR* var;
918 
919  consdata = SCIPconsGetData(cons);
920  assert(consdata != NULL);
921  assert(eventhdlr != NULL);
922  assert(0 <= pos && pos < consdata->nvars);
923  assert(consdata->vars != NULL);
924 
925  var = consdata->vars[pos];
926  assert(var != NULL);
927 
928  /* we are catching the following events:
929  *
930  * - SCIP_EVENTTYPE_BOUNDCHANGED: Is used to count the number of variable fixed locally to zero and one. That helps
931  * to speed up the propagation
932  *
933  * - SCIP_EVENTTYPE_VARDELETED: Is caught to remove a deleted variable from the constraint
934  *
935  * - SCIP_EVENTTYPE_VARFIXED: Is used to get informed if a variable of the constraint was aggregated which means was
936  * detected to be equal or a negated variable of on other variable. in case of a negation
937  * this could lead to a redundant constraint if the (other) active variable is also part
938  * of the constraint.
939  */
941 
942  /* catch bound change events on variable */
943  SCIP_CALL( SCIPcatchVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) );
944 
945  /* update the fixed variables counters for this variable */
946  if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
947  {
948  consdata->nfixedzeros++;
949 
950  /* during presolving, we may fix the last unfixed variable or do an aggregation if there are two unfixed variables */
951  if( SCIPconsIsActive(cons) && ((SCIPgetStage(scip) < SCIP_STAGE_INITSOLVE) && (consdata->nfixedzeros >= consdata->nvars - 2)) )
952  {
953  consdata->presolpropagated = FALSE;
954 
955  /* during solving, we only propagate again if there is only one unfixed variable left */
956  if( consdata->nfixedzeros >= consdata->nvars - 1 )
957  {
958  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
959  }
960  }
961  }
962  else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
963  {
964  consdata->nfixedones++;
965 
966  if( SCIPconsIsActive(cons) )
967  {
968  consdata->presolpropagated = FALSE;
969  SCIP_CALL( SCIPmarkConsPropagate(scip, cons) );
970  }
971  }
972 
973  return SCIP_OKAY;
974 }
975 
976 /** drops events for variable at given position */
977 static
979  SCIP* scip, /**< SCIP data structure */
980  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
981  SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
982  int pos /**< array position of variable to catch bound change events for */
983  )
984 {
985  SCIP_CONSDATA* consdata;
986  SCIP_EVENTTYPE eventtype;
987  SCIP_VAR* var;
988 
989  consdata = SCIPconsGetData(cons);
990  assert(consdata != NULL);
991  assert(eventhdlr != NULL);
992  assert(0 <= pos && pos < consdata->nvars);
993  assert(consdata->vars != NULL);
994 
995  var = consdata->vars[pos];
996  assert(var != NULL);
997 
999 
1000  /* drop events on variable */
1001  SCIP_CALL( SCIPdropVarEvent(scip, var, eventtype, eventhdlr, (SCIP_EVENTDATA*)cons, -1) );
1002 
1003  /* update the fixed variables counters for this variable */
1004  if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
1005  consdata->nfixedzeros--;
1006  else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
1007  consdata->nfixedones--;
1008 
1009  return SCIP_OKAY;
1010 }
1011 
1012 /** catches bound change events for all variables in transformed setppc constraint */
1013 static
1015  SCIP* scip, /**< SCIP data structure */
1016  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1017  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1018  )
1019 {
1020  SCIP_CONSDATA* consdata;
1021  int i;
1023  consdata = SCIPconsGetData(cons);
1024  assert(consdata != NULL);
1025 
1026  if( consdata->catchevents == TRUE )
1027  return SCIP_OKAY;
1028 
1029  /* catch event for every single variable */
1030  for( i = 0; i < consdata->nvars; ++i )
1031  {
1032  SCIP_CALL( catchEvent(scip, cons, eventhdlr, i) );
1033  }
1034 
1035  consdata->catchevents = TRUE;
1036 
1037  return SCIP_OKAY;
1038 }
1039 
1040 /** drops bound change events for all variables in transformed setppc constraint */
1041 static
1043  SCIP* scip, /**< SCIP data structure */
1044  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1045  SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
1046  )
1047 {
1048  SCIP_CONSDATA* consdata;
1049  int i;
1051  consdata = SCIPconsGetData(cons);
1052  assert(consdata != NULL);
1053 
1054  if( consdata->catchevents == FALSE )
1055  return SCIP_OKAY;
1056 
1057  /* drop event of every single variable */
1058  for( i = 0; i < consdata->nvars; ++i )
1059  {
1060  SCIP_CALL( dropEvent(scip, cons, eventhdlr, i) );
1061  }
1062 
1063  consdata->catchevents = FALSE;
1064 
1065  return SCIP_OKAY;
1066 }
1067 
1068 /** adds coefficient in setppc constraint */
1069 static
1071  SCIP* scip, /**< SCIP data structure */
1072  SCIP_CONS* cons, /**< setppc constraint */
1073  SCIP_VAR* var /**< variable to add to the constraint */
1074  )
1075 {
1076  SCIP_CONSDATA* consdata;
1077  SCIP_Bool transformed;
1079  assert(var != NULL);
1080 
1081  consdata = SCIPconsGetData(cons);
1082  assert(consdata != NULL);
1083 
1084  /* are we in the transformed problem? */
1085  transformed = SCIPconsIsTransformed(cons);
1086 
1087  /* always use transformed variables in transformed constraints */
1088  if( transformed )
1089  {
1090  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
1091  }
1092  assert(var != NULL);
1093  assert(transformed == SCIPvarIsTransformed(var));
1094 
1095  SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
1096  consdata->vars[consdata->nvars] = var;
1097  consdata->nvars++;
1098  if( consdata->validsignature )
1099  consdata->signature |= SCIPhashSignature64(SCIPvarGetIndex(var));
1100  consdata->sorted = (consdata->nvars == 1);
1101  consdata->changed = TRUE;
1102 
1103  /* capture the variable */
1104  SCIP_CALL( SCIPcaptureVar(scip, var) );
1105 
1106  /* if we are in transformed problem, catch the variable's events */
1107  if( transformed )
1108  {
1109  SCIP_CONSHDLR* conshdlr;
1110  SCIP_CONSHDLRDATA* conshdlrdata;
1111 
1112  /* get event handler */
1113  conshdlr = SCIPconsGetHdlr(cons);
1114  assert(conshdlr != NULL);
1115  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1116  assert(conshdlrdata != NULL);
1117  assert(conshdlrdata->eventhdlr != NULL);
1118 
1119  /* catch bound change events of variable */
1120  if( consdata->catchevents )
1121  {
1122  SCIP_CALL( catchEvent(scip, cons, conshdlrdata->eventhdlr, consdata->nvars-1) );
1123  }
1124 
1125  if( !consdata->existmultaggr && SCIPvarGetStatus(SCIPvarGetProbvar(var)) == SCIP_VARSTATUS_MULTAGGR )
1126  consdata->existmultaggr = TRUE;
1127 
1128 #ifdef VARUSES
1129  /* if the constraint is currently active, increase the variable usage counter */
1130  if( SCIPconsIsActive(cons) )
1131  {
1132  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var) );
1133  }
1134 #endif
1135  }
1136 
1137  /* install the rounding locks for the new variable */
1138  SCIP_CALL( lockRounding(scip, cons, var) );
1139 
1140  /* add the new coefficient to the LP row */
1141  if( consdata->row != NULL )
1142  {
1143  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, 1.0) );
1144  }
1145 
1146  consdata->merged = FALSE;
1147  consdata->cliqueadded = FALSE;
1148 
1149  return SCIP_OKAY;
1150 }
1151 
1152 /** deletes coefficient at given position from setppc constraint data */
1153 static
1155  SCIP* scip, /**< SCIP data structure */
1156  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1157  int pos /**< position of coefficient to delete */
1158  )
1159 {
1160  SCIP_CONSDATA* consdata;
1161  SCIP_VAR* var;
1163  assert(scip != NULL);
1164  assert(cons != NULL);
1165 
1166  consdata = SCIPconsGetData(cons);
1167  assert(consdata != NULL);
1168  assert(0 <= pos && pos < consdata->nvars);
1169 
1170  var = consdata->vars[pos];
1171  assert(var != NULL);
1172  assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
1173 
1174  /* remove the rounding locks for the deleted variable */
1175  SCIP_CALL( unlockRounding(scip, cons, var) );
1176 
1177  /* if we are in transformed problem, delete the event data of the variable */
1178  if( SCIPconsIsTransformed(cons) )
1179  {
1180  SCIP_CONSHDLR* conshdlr;
1181  SCIP_CONSHDLRDATA* conshdlrdata;
1182 
1183  /* get event handler */
1184  conshdlr = SCIPconsGetHdlr(cons);
1185  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1186  assert(conshdlrdata != NULL);
1187  assert(conshdlrdata->eventhdlr != NULL);
1188 
1189  /* drop bound change events of variable */
1190  if( consdata->catchevents )
1191  {
1192  SCIP_CALL( dropEvent(scip, cons, conshdlrdata->eventhdlr, pos) );
1193  }
1194 
1195  /* the last variable of the constraint was deleted; mark it for propagation (so that it can be deleted) */
1196  if( consdata->nvars == 1 )
1197  {
1198  consdata->presolpropagated = FALSE;
1199  }
1200  }
1201 
1202  /* delete coefficient from the LP row */
1203  if( consdata->row != NULL )
1204  {
1205  SCIP_CALL( SCIPaddVarToRow(scip, consdata->row, var, -1.0) );
1206  }
1207 
1208  /* move the last variable to the free slot */
1209  if( pos != consdata->nvars - 1 )
1210  {
1211  consdata->vars[pos] = consdata->vars[consdata->nvars-1];
1212  consdata->sorted = FALSE;
1213  }
1214  consdata->nvars--;
1215  consdata->validsignature = FALSE;
1216  consdata->changed = TRUE;
1217 
1218  /* release variable */
1219  SCIP_CALL( SCIPreleaseVar(scip, &var) );
1220 
1221  return SCIP_OKAY;
1222 }
1223 
1224 /** preform dual presolving
1225  *
1226  * In case a part (more than one variable) in the setppc constraint is independent of everything else (is locked only by
1227  * this constraint), we can perform dual reductions:
1228  *
1229  * (1) set covering
1230  *
1231  * - fix all independent variables with negative object coefficient to one
1232  * - fix all remaining independent variables to zero
1233  *
1234  * (i) all variables are independent and the constraint is not modifiable
1235  *
1236  * - fix the variable with the smallest object coefficient to one
1237  *
1238  * (ii) a variable x has exactly 0 uplocks and arbitrary downlocks and a variable y has exactly 1 downlock and
1239  * arbitrary uplocks and obj(x) <= obj(y) and obj(y) >= 0
1240  *
1241  * - fix y to 0, because it is dominated by x
1242  *
1243  * (2) set partitioning
1244  *
1245  * (i) all variables are independent and the constraint is not modifiable
1246  *
1247  * - fix the variable with the smallest object coefficient to one
1248  * - fix all remaining independent variables to zero
1249  *
1250  * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 1 downlock and
1251  * arbitrary uplocks and obj(x) <= obj(y)
1252  *
1253  * - fix y to 0, because it is dominated by x
1254  *
1255  * (3) set packing
1256  *
1257  * (i) all variables are independent and the constraint is not modifiable
1258  *
1259  * - fix the variable with the smallest object coefficient to one if the object coefficient is negative or zero
1260  * - fix all remaining independent variables to zero
1261  *
1262  * (ii) a variable x has exactly 1 uplock and arbitrary downlocks and a variable y has exactly 0 downlocks and
1263  * arbitrary uplocks and obj(x) <= obj(y)
1264  *
1265  * - fix y to 0, because it is dominated by x
1266  *
1267  *
1268  * Note: the following dual reduction for set covering and set packing constraints is already performed by the presolver
1269  * "dualfix"
1270  * (1) in case of a set covering constraint the following dual reduction can be performed:
1271  * - if a variable in a set covering constraint is only locked by that constraint and has negative or zero
1272  * objective coefficient than it can be fixed to one
1273  * (2) in case of a set packing constraint the following dual reduction can be performed:
1274  * - if a variable in a set packing constraint is only locked by that constraint and has positive or zero
1275  * objective coefficient than it can be fixed to zero
1276  *
1277  * Note: all dual reduction (ii) could also be performed by the "domcol" presolver, but because the pairwise comparison of
1278  * columns is only done heuristically (and here it should be even cheaper) we perform them here (too).
1279  *
1280  * Moreover, if there exists a variable that is only locked by a covering or packing constraint with two variables, one
1281  * can aggregate variables.
1282  */
1283 static
1285  SCIP* scip, /**< SCIP data structure */
1286  SCIP_CONS* cons, /**< setppc constraint */
1287  int* nfixedvars, /**< pointer to count number of fixings */
1288  int* ndelconss, /**< pointer to count number of deleted constraints */
1289  int* naggrvars, /**< pointer to count number of variables aggregated */
1290  SCIP_RESULT* result /**< pointer to store the result SCIP_SUCCESS, if presolving was performed */
1291  )
1293  SCIP_CONSDATA* consdata;
1294  SCIP_SETPPCTYPE setppctype;
1295  SCIP_VAR** vars;
1296  SCIP_VAR* activevar;
1297  SCIP_VAR* var;
1298  SCIP_Real bestobjval;
1299  SCIP_Real objval;
1300  SCIP_Real objsign;
1301  SCIP_Real fixval;
1302  SCIP_Bool infeasible;
1303  SCIP_Bool fixed;
1304  SCIP_Bool negated;
1305  int noldfixed;
1306  int nposfixings;
1307  int nlockdowns;
1308  int nlockups;
1309  int nvars;
1310  int indepidx = -1;
1311  int idx;
1312  int v;
1313 
1314  assert(scip != NULL);
1315  assert(cons != NULL);
1316  assert(nfixedvars != NULL);
1317  assert(ndelconss != NULL);
1318  assert(result != NULL);
1319 
1320  /* constraints for which the check flag is set to FALSE, did not contribute to the lock numbers; therefore, we cannot
1321  * use the locks to decide for a dual reduction using this constraint; for example after a restart the cuts which are
1322  * added to the problems have the check flag set to FALSE
1323  */
1324  if( !SCIPconsIsChecked(cons) )
1325  return SCIP_OKAY;
1326 
1327  assert(SCIPconsIsActive(cons));
1328 
1329  consdata = SCIPconsGetData(cons);
1330  assert(consdata != NULL);
1331 
1332  /* modifiable non-covering constraints cannot be deleted if one variable is fixed to one, because the propagation for
1333  * newly inserted variables must be considered later
1334  */
1335  if( consdata->nfixedones == 1 && SCIPconsIsModifiable(cons) )
1336  return SCIP_OKAY;
1337 
1338  /* all fixed variables should be removed at that point */
1339  assert(consdata->nfixedones == 0);
1340  assert(consdata->nfixedzeros == 0);
1341 
1342  nvars = consdata->nvars;
1343 
1344  /* we don't want to consider small constraints (note that the constraints can be modifiable, so we can't delete this
1345  * constraint)
1346  */
1347  if( nvars < 2 )
1348  return SCIP_OKAY;
1349 
1350  setppctype = (SCIP_SETPPCTYPE)consdata->setppctype;
1351  vars = consdata->vars;
1352  idx = -1;
1353  bestobjval = SCIP_INVALID;
1354 
1355  /* collect the rounding locks depending on the setppc type */
1356  switch( setppctype )
1357  {
1359  nlockdowns = 1;
1360  nlockups = 1;
1361  objsign = 0.0;
1362  break;
1364  nlockdowns = 0;
1365  nlockups = 1;
1366  objsign = -1.0;
1367  break;
1369  nlockdowns = 1;
1370  nlockups = 0;
1371  objsign = 1.0;
1372  break;
1373  default:
1374  SCIPerrorMessage("unknown setppc type\n");
1375  SCIPABORT();
1376  return SCIP_INVALIDDATA; /*lint !e527*/
1377  }
1378 
1379  nposfixings = 0;
1380 
1381  /* check if we can apply the dual reduction; therefore count the number of variables where the setppc has the only
1382  * locks on this constraint
1383  */
1384  for( v = 0; v < nvars; ++v )
1385  {
1386  var = vars[v];
1387  assert(var != NULL);
1388 
1389  /* the variable should not be (globally) fixed */
1390  assert(SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5);
1391 
1392  if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) >= nlockdowns
1393  && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == nlockups )
1394  {
1395  activevar = var;
1396  negated = FALSE;
1397 
1398  /* get the active variable */
1399  SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
1400  assert(SCIPvarIsActive(activevar));
1401 
1402  if( negated )
1403  objval = -SCIPvarGetObj(activevar);
1404  else
1405  objval = SCIPvarGetObj(activevar);
1406 
1407  /* check if the current variable has a smaller objective coefficient */
1408  if( idx == -1 || objval < bestobjval )
1409  {
1410  idx = v;
1411  bestobjval = objval;
1412  }
1413 
1414  /* determine independent variable, i.e., only locked by the current constraint */
1415  if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns )
1416  {
1417  assert(SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == nlockups);
1418 
1419  /* store variables that have the right objective sign */
1420  if ( objval * objsign >= 0.0 )
1421  indepidx = v;
1422  }
1423  }
1424 
1425  /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1426  * variables
1427  */
1428  if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
1429  && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
1430  ++nposfixings;
1431  }
1432 
1433  if( idx == -1 || nposfixings == 0 )
1434  return SCIP_OKAY;
1435 
1436  SCIPdebugMsg(scip, "dual fixing constraint: \n");
1437  SCIPdebug( SCIP_CALL( SCIPprintCons(scip, cons, NULL) ) );
1438  SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") );
1439 
1440  assert(idx >= 0 && idx < nvars);
1441  assert(bestobjval < SCIPinfinity(scip));
1442 
1443  noldfixed = *nfixedvars;
1444 
1445  /* In the special case of two variables, where one variable is independent and will be minimized for covering or
1446  * maximized for packing or does not appear in the objective, we can aggregate variables:
1447  * - Covering: var1 + var2 >= 1 and the objective of var1 is non-negative.
1448  * - Packing: var1 + var2 <= 1 and the objective of var1 is non-positive.
1449  * In both cases, var1 + var2 = 1 holds in every optimal solution.
1450  */
1451  if( setppctype != SCIP_SETPPCTYPE_PARTITIONING && nvars == 2 && indepidx >= 0 )
1452  {
1453  SCIP_Bool redundant;
1454  SCIP_Bool aggregated;
1455  int idx2;
1456 
1457  idx2 = 1 - indepidx;
1458  assert( 0 <= idx2 && idx2 < 2 );
1459 
1460  SCIP_CALL( SCIPaggregateVars(scip, vars[indepidx], vars[idx2], 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
1461  assert(!infeasible);
1462  assert(redundant);
1463  assert(aggregated);
1464  ++(*naggrvars);
1465 
1466  /* remove constraint since it is redundant */
1467  SCIP_CALL( SCIPdelCons(scip, cons) );
1468  ++(*ndelconss);
1469 
1470  *result = SCIP_SUCCESS;
1471 
1472  return SCIP_OKAY;
1473  }
1474 
1475  /* in case of set packing and set partitioning we fix the dominated variables to zero */
1476  if( setppctype != SCIP_SETPPCTYPE_COVERING )
1477  {
1478  /* first part of all variables */
1479  for( v = nvars - 1; v >= 0; --v )
1480  {
1481  if( v == idx )
1482  continue;
1483 
1484  var = vars[v];
1485  assert(var != NULL);
1486 
1487  /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1488  * variables
1489  */
1490  if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
1491  && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
1492  {
1493  activevar = var;
1494  negated = FALSE;
1495 
1496  /* get the active variable */
1497  SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
1498  assert(SCIPvarIsActive(activevar));
1499 
1500  if( negated )
1501  objval = -SCIPvarGetObj(activevar);
1502  else
1503  objval = SCIPvarGetObj(activevar);
1504 
1505  if( objval >= bestobjval )
1506  {
1507  SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
1508  assert(!infeasible);
1509  assert(fixed);
1510 
1511  SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == 0.0\n", SCIPvarGetName(var));
1512  ++(*nfixedvars);
1513  }
1514  }
1515  }
1516  }
1517  /* if we got a set covering constraint and not all variables are locked from this constraint it might not get
1518  * redundant (which is case if it is not possible to fix at least one variable to one), we fix all redundant
1519  * variables to their best bound
1520  */
1521  else
1522  {
1523  /* first part of all variables */
1524  for( v = nvars - 1; v >= 0; --v )
1525  {
1526  if( v == idx )
1527  continue;
1528 
1529  var = vars[v];
1530  assert(var != NULL);
1531 
1532  /* in case another constraint has also downlocks on that variable we cannot perform a dual reduction on these
1533  * variables
1534  */
1535  if( SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == nlockdowns
1536  && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) >= nlockups )
1537  {
1538  activevar = var;
1539  negated = FALSE;
1540 
1541  /* get the active variable */
1542  SCIP_CALL( SCIPvarGetProbvarBinary(&activevar, &negated) );
1543  assert(SCIPvarIsActive(activevar));
1544  assert(negated
1547  assert(!negated
1550 
1551  if( negated )
1552  objval = -SCIPvarGetObj(activevar);
1553  else
1554  objval = SCIPvarGetObj(activevar);
1555 
1556  if( objval > 0.0 )
1557  fixval = 0.0;
1558  else
1559  fixval = 1.0;
1560 
1561  /* if variables has a negative objective contribution, and is uplocked by another constraint we cannot fix
1562  * the variables to 1
1563  */
1564  if( (fixval == 1.0 && SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) > nlockups) || objval < bestobjval )
1565  continue;
1566 
1567  SCIP_CALL( SCIPfixVar(scip, var, fixval, &infeasible, &fixed) );
1568  assert(!infeasible);
1569  assert(fixed);
1570 
1571  SCIPdebugMsg(scip, " -> dual-fixed dominated variable <%s> == %g\n", SCIPvarGetName(var), fixval);
1572  ++(*nfixedvars);
1573  }
1574  }
1575  }
1576 
1577  /* if all variables but the domination variable is fixed and the constraint is not modifiable or the constraint is a
1578  * covering constraint and the bestobjval is less than or equal to zero, we can fix the domination variable (with best
1579  * objective coefficient) and the constraint gets redundant
1580  */
1581  if( ((*nfixedvars - noldfixed == nvars - 1) && !SCIPconsIsModifiable(cons)) || (setppctype == SCIP_SETPPCTYPE_COVERING && bestobjval <= 0.0) )
1582  {
1583  /* in case of a set packing constraint with positive objective values, all variables can be fixed to zero; in all
1584  * other cases the variable with the smallest objective values is fixed to one
1585  */
1586  if( (setppctype == SCIP_SETPPCTYPE_PACKING && bestobjval > 0.0
1587  && SCIPvarGetNLocksDownType(vars[idx], SCIP_LOCKTYPE_MODEL) == 0)
1588  || setppctype != SCIP_SETPPCTYPE_PACKING || bestobjval <= 0.0 )
1589  {
1590  if( setppctype == SCIP_SETPPCTYPE_PACKING && bestobjval > 0.0 )
1591  fixval = 0.0;
1592  else
1593  fixval = 1.0;
1594 
1595  SCIP_CALL( SCIPfixVar(scip, vars[idx], fixval, &infeasible, &fixed) );
1596  assert(!infeasible);
1597  assert(fixed);
1598 
1599  SCIPdebugMsg(scip, " -> dual-fixed best variable <%s> == %g\n", SCIPvarGetName(vars[idx]), fixval);
1600  ++(*nfixedvars);
1601  }
1602 
1603  /* check that we really have a non-violated constraint in hand before deleting */
1604  assert((setppctype == SCIP_SETPPCTYPE_PACKING && consdata->nfixedones <= 1) ||
1605  (setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedones == 1) ||
1606  (setppctype == SCIP_SETPPCTYPE_COVERING && consdata->nfixedones >= 1));
1607 
1608  /* remove constraint since it is redundant */
1609  SCIP_CALL( SCIPdelCons(scip, cons) );
1610  ++(*ndelconss);
1611  }
1612 
1613  assert(*nfixedvars >= noldfixed);
1614 
1615  /* set result pointer to SCIP_SUCCESS, if variables could be fixed */
1616  if( *nfixedvars != noldfixed )
1617  *result = SCIP_SUCCESS;
1618 
1619  return SCIP_OKAY;
1620 }
1621 
1622 /** find pairs of negated variables in constraint:
1623  * partitioning/packing: all other variables must be zero, constraint is redundant
1624  * covering: constraint is redundant
1625  *
1626  * find sets of equal variables in constraint:
1627  * partitioning/packing: variable must be zero
1628  * covering: multiple entries of variable can be replaced by single entry
1629  */
1630 static
1632  SCIP* scip, /**< SCIP data structure */
1633  SCIP_CONS* cons, /**< knapsack constraint */
1634  int* nfixedvars, /**< pointer to store number of fixed variables */
1635  int* ndelconss, /**< pointer to store number of deleted constraints */
1636  int* nchgcoefs, /**< pointer to store number of changed coefficients */
1637  SCIP_Bool* cutoff /**< pointer to store whether a fixing leads to a cutoff */
1638  )
1640  SCIP_CONSDATA* consdata;
1641  int v;
1642 
1643  assert(scip != NULL);
1644  assert(cons != NULL);
1645  assert(nfixedvars != NULL);
1646  assert(ndelconss != NULL);
1647  assert(nchgcoefs != NULL);
1648  assert(cutoff != NULL);
1649 
1650  consdata = SCIPconsGetData(cons);
1651  assert(consdata != NULL);
1652 
1653  if( consdata->merged || SCIPconsIsDeleted(cons) )
1654  return SCIP_OKAY;
1655 
1656  if( consdata->nvars <= 1 )
1657  {
1658  consdata->merged = TRUE;
1659  return SCIP_OKAY;
1660  }
1661 
1662  assert(consdata->vars != NULL || consdata->nvars == 0);
1663 
1664  /* sorting array after indices of variables, that's only for faster merging */
1665  SCIPsortPtr((void**)consdata->vars, SCIPvarCompActiveAndNegated, consdata->nvars);
1666  /* setppc sorting now lost */
1667  consdata->sorted = FALSE;
1668 
1669  /* loop backwards through the items: deletion only affects rear items */
1670  for( v = consdata->nvars - 1; v > 0; --v )
1671  {
1672  SCIP_VAR* var1;
1673  SCIP_VAR* var2;
1674  SCIP_Bool negated1;
1675  SCIP_Bool negated2;
1676 
1677  negated1 = FALSE;
1678  negated2 = FALSE;
1679 
1680  var1 = consdata->vars[v];
1681  assert(SCIPvarIsBinary(var1));
1684  {
1685  var1 = SCIPvarGetNegatedVar(var1);
1686  negated1 = TRUE;
1687  }
1688  assert(var1 != NULL);
1689 
1690  var2 = consdata->vars[v-1];
1691  assert(SCIPvarIsBinary(var2));
1694  {
1695  var2 = SCIPvarGetNegatedVar(var2);
1696  negated2 = TRUE;
1697  }
1698  assert(var2 != NULL);
1699 
1700  if( var1 == var2 )
1701  {
1702  SCIP_Bool infeasible;
1703  SCIP_Bool fixed;
1704 
1705  /* one variables is active and the other is the same negated variable */
1706  if( negated1 != negated2 )
1707  {
1708  /* all other variable have to be zero if it's a partitioning or packing constraint */
1709  if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
1710  {
1711  int i;
1712 
1713  assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
1714  || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
1715 
1716  for( i = consdata->nvars - 1; i >= 0; --i )
1717  if( i != v && i != (v-1) )
1718  {
1719  SCIP_CALL( SCIPfixVar(scip, consdata->vars[i], 0.0, &infeasible, &fixed) );
1720  if( infeasible )
1721  {
1722  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
1723  SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[i]));
1724  *cutoff = TRUE;
1725  return SCIP_OKAY;
1726  }
1727 
1728  if( fixed )
1729  ++(*nfixedvars);
1730  }
1731  }
1732  /* all setppc-type constraints are redundant */
1733  SCIP_CALL( SCIPdelCons(scip, cons) );
1734  ++(*ndelconss);
1735  return SCIP_OKAY;
1736  }
1737  /* both variables are either active or negated */
1738  else
1739  {
1740  /* this variable can be fixed to zero if it's a partitioning or packing constraint */
1741  if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
1742  {
1743  assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
1744  || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
1745 
1746  SCIP_CALL( SCIPfixVar(scip, var1, negated1 ? 1.0 : 0.0, &infeasible, &fixed) );
1747  if( infeasible )
1748  {
1749  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == %g\n",
1750  SCIPconsGetName(cons), SCIPvarGetName(var1), negated1 ? 1.0 : 0.0);
1751  *cutoff = TRUE;
1752  return SCIP_OKAY;
1753  }
1754 
1755  if( fixed )
1756  ++(*nfixedvars);
1757  }
1758  /* multiple entries of variable can be replaced by single entry */
1759  else
1760  {
1761  SCIP_CALL( delCoefPos(scip, cons, v) ); /* only some changed behind position v-1, so it's okay */
1762  ++(*nchgcoefs);
1763  }
1764  }
1765  consdata->changed = TRUE;
1766  }
1767  }
1768  consdata->merged = TRUE;
1769 
1770  return SCIP_OKAY;
1771 }
1772 
1773 /** deletes all zero-fixed variables and replace aggregated variables */
1774 static
1776  SCIP* scip, /**< SCIP data structure */
1777  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint */
1778  int* naddconss, /**< pointer to count number of added constraints, or NULL indicating we
1779  * can not resolve multi-aggregations
1780  */
1781  int* ndelconss, /**< pointer to count number of deleted constraints, or NULL indicating we
1782  * can not resolve multi-aggregations
1783  */
1784  int* nfixedvars, /**< pointer to store number of fixed variables, or NULL indicating we can
1785  * not resolve multi-aggregations
1786  */
1787  SCIP_Bool* cutoff /**< pointer to store whether a fixing leads to a cutoff, or NULL
1788  * indicating we can not resolve multi-aggregations
1789  */
1790  )
1791 {
1792  SCIP_CONSDATA* consdata;
1793  int v;
1794 
1795  assert(scip != NULL);
1796  assert(cons != NULL);
1797 
1798  consdata = SCIPconsGetData(cons);
1799  assert(consdata != NULL);
1800 
1801  /* all multi-aggregations should be resolved */
1802  consdata->existmultaggr = FALSE;
1803 
1804  v = 0;
1805  while( v < consdata->nvars )
1806  {
1807  SCIP_VAR* var;
1808 
1809  var = consdata->vars[v];
1810  assert(SCIPvarIsBinary(var));
1811 
1812  if( SCIPvarGetUbGlobal(var) < 0.5 )
1813  {
1814  assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
1815  SCIP_CALL( delCoefPos(scip, cons, v) );
1816  }
1817  else
1818  {
1819  SCIP_VAR* repvar;
1820  SCIP_Bool negated;
1821 
1822  /* get binary representative of variable */
1823  SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
1824 
1825  /* resolve multi-aggregation */
1827  {
1828  SCIP_VAR** consvars;
1829  SCIP_Real* consvals;
1830  SCIP_Real constant = 0.0;
1831  SCIP_Bool easycase;
1832  int nconsvars;
1833  int requiredsize;
1834  int v2;
1835 
1836  nconsvars = 1;
1837  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, 1) );
1838  SCIP_CALL( SCIPallocBufferArray(scip, &consvals, 1) );
1839  consvars[0] = repvar;
1840  consvals[0] = 1.0;
1841 
1842  /* get active variables for new constraint */
1843  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, nconsvars, &constant, &requiredsize, TRUE) );
1844  /* if space was not enough we need to resize the buffers */
1845  if( requiredsize > nconsvars )
1846  {
1847  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
1848  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );
1849 
1850  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1851  assert(requiredsize <= nconsvars);
1852  }
1853 
1854  easycase = FALSE;
1855 
1856  if( SCIPisZero(scip, constant) )
1857  {
1858  /* add active representation */
1859  for( v2 = nconsvars - 1; v2 >= 0; --v2 )
1860  {
1861  if( !SCIPvarIsBinary(consvars[v2]) )
1862  break;
1863 
1864  if( !SCIPisEQ(scip, consvals[v2], 1.0) )
1865  break;
1866  }
1867 
1868  if( v2 < 0 )
1869  easycase = TRUE;
1870  }
1871  else if( SCIPisFeasEQ(scip, constant, 1.0) )
1872  {
1873  /* check for another multi-aggregation */
1874  for( v2 = consdata->nvars - 1; v2 > v; --v2 )
1875  {
1876  if( SCIPvarGetStatus(SCIPvarGetProbvar(consdata->vars[v])) == SCIP_VARSTATUS_MULTAGGR )
1877  break;
1878  }
1879 
1880  /* constraint is redundant */
1881  if( v2 == v && nconsvars == 0 )
1882  {
1883  /* we can fix */
1884  if( consdata->nvars > 1 && (SCIP_SETPPCTYPE)consdata->setppctype != SCIP_SETPPCTYPE_COVERING )
1885  {
1886  if( nfixedvars != NULL )
1887  {
1888  SCIP_Bool fixed;
1889 
1890  assert(cutoff != NULL);
1891 
1892  for( v2 = consdata->nvars - 1; v2 >= 0; --v2 )
1893  {
1894  if( consdata->vars[v2] != var )
1895  {
1896  SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(consdata->vars[v2]));
1897 
1898  /* fix all remaining variables to zero, constraint is already feasible or infeasible */
1899  SCIP_CALL( SCIPfixVar(scip, consdata->vars[v2], 0.0, cutoff, &fixed) );
1900  if( *cutoff )
1901  {
1902  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
1903  SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v2]));
1904 
1905  SCIPfreeBufferArray(scip, &consvals);
1906  SCIPfreeBufferArray(scip, &consvars);
1907 
1908  goto TERMINATE;
1909  }
1910 
1911  if( fixed )
1912  ++(*nfixedvars);
1913  }
1914  }
1915  }
1916  }
1917 
1918  if( ndelconss != NULL && (nfixedvars != NULL || consdata->nvars == 1 || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING) )
1919  {
1920  /* delete old constraint */
1921  SCIP_CALL( SCIPdelCons(scip, cons) );
1922  ++(*ndelconss);
1923  }
1924  SCIPfreeBufferArray(scip, &consvals);
1925  SCIPfreeBufferArray(scip, &consvars);
1926 
1927  goto TERMINATE;
1928  }
1929  }
1930 
1931  /* we can easily add the coefficients and still have a setppc constraint */
1932  if( easycase )
1933  {
1934  /* delete old (multi-aggregated) variable */
1935  SCIP_CALL( delCoefPos(scip, cons, v) );
1936 
1937  /* add active representation */
1938  for( v2 = nconsvars - 1; v2 >= 0; --v2 )
1939  {
1940  assert(SCIPvarIsBinary(consvars[v2]));
1941  assert(SCIPvarIsActive(consvars[v2]) || (SCIPvarGetStatus(consvars[v2]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(consvars[v2]))));
1942 
1943  SCIP_CALL( addCoef(scip, cons, consvars[v2]) );
1944  }
1945  }
1946  /* we need to degrade this setppc constraint to a linear constraint */
1947  else if( (ndelconss != NULL && naddconss != NULL) || SCIPconsIsAdded(cons) )
1948  {
1949  char name[SCIP_MAXSTRLEN];
1950  SCIP_CONS* newcons;
1951  SCIP_Real lhs;
1952  SCIP_Real rhs;
1953  int size;
1954  int k;
1955 
1956  /* it might happen that there are more than one multi-aggregated variable, so we need to get the whole
1957  * probvar sum over all variables
1958  */
1959 
1960  size = MAX(nconsvars, 1) + consdata->nvars - 1;
1961 
1962  /* memory needed is at least old number of variables - 1 + number of variables in first multi-aggregation */
1963  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, size) );
1964  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, size) );
1965 
1966  nconsvars = consdata->nvars;
1967 
1968  /* add constraint variables to new linear variables */
1969  for( k = consdata->nvars - 1; k >= 0; --k )
1970  {
1971  consvars[k] = consdata->vars[k];
1972  consvals[k] = 1.0;
1973  }
1974 
1975  constant = 0.0;
1976 
1977  /* get active variables for new constraint */
1978  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, size, &constant, &requiredsize, TRUE) );
1979 
1980  /* if space was not enough (we found another multi-aggregation), we need to resize the buffers */
1981  if( requiredsize > nconsvars )
1982  {
1983  SCIP_CALL( SCIPreallocBufferArray(scip, &consvars, requiredsize) );
1984  SCIP_CALL( SCIPreallocBufferArray(scip, &consvals, requiredsize) );
1985 
1986  SCIP_CALL( SCIPgetProbvarLinearSum(scip, consvars, consvals, &nconsvars, requiredsize, &constant, &requiredsize, TRUE) );
1987  assert(requiredsize <= nconsvars);
1988  }
1989 
1990  /* compute sides */
1991  if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
1992  {
1993  lhs = -SCIPinfinity(scip);
1994  rhs = 1.0 - constant;
1995  }
1996  else if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING )
1997  {
1998  lhs = 1.0 - constant;
1999  rhs = 1.0 - constant;
2000  }
2001  else
2002  {
2003  assert((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING);
2004  lhs = 1.0 - constant;
2005  rhs = SCIPinfinity(scip);
2006  }
2007 
2008  /* create linear constraint */
2009  (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s", SCIPconsGetName(cons));
2010  SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, nconsvars, consvars, consvals, lhs, rhs,
2011  SCIPconsIsInitial(cons),
2015  SCIP_CALL( SCIPaddCons(scip, newcons) );
2016 
2017  SCIPdebugMsg(scip, "added linear constraint: ");
2018  SCIPdebugPrintCons(scip, newcons, NULL);
2019  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2020 
2021  SCIPfreeBufferArray(scip, &consvals);
2022  SCIPfreeBufferArray(scip, &consvars);
2023 
2024  /* delete old constraint */
2025  SCIP_CALL( SCIPdelCons(scip, cons) );
2026  if( ndelconss != NULL && naddconss != NULL )
2027  {
2028  ++(*ndelconss);
2029  ++(*naddconss);
2030  }
2031 
2032  goto TERMINATE;
2033  }
2034  /* we need to degrade this setppc constraint to a linear constraint*/
2035  else
2036  {
2037  /* check, if the variable should be replaced with the representative */
2038  if( repvar != var )
2039  {
2040  /* delete old (aggregated) variable */
2041  SCIP_CALL( delCoefPos(scip, cons, v) );
2042 
2043  /* add representative instead */
2044  SCIP_CALL( addCoef(scip, cons, repvar) );
2045  }
2046 
2047  SCIPwarningMessage(scip, "setppc constraint <%s> has a multi-aggregated variable, which was not resolved and therefore could lead to aborts\n", SCIPconsGetName(cons));
2048  ++v;
2049  }
2050 
2051  SCIPfreeBufferArray(scip, &consvals);
2052  SCIPfreeBufferArray(scip, &consvars);
2053  }
2054  else
2055  {
2056  /* check, if the variable should be replaced with the representative */
2057  if( repvar != var )
2058  {
2059  /* delete old (aggregated) variable */
2060  SCIP_CALL( delCoefPos(scip, cons, v) );
2061 
2062  /* add representative instead */
2063  SCIP_CALL( addCoef(scip, cons, repvar) );
2064  }
2065  else
2066  ++v;
2067  }
2068  }
2069  }
2070 
2071  TERMINATE:
2072  /* all multi-aggregations should be resolved */
2073  consdata->existmultaggr = FALSE;
2074 
2075  return SCIP_OKAY;
2076 }
2077 
2078 /** analyzes conflicting assignment on given constraint where all of the variables where assigned to zero,
2079  * and adds conflict constraint to problem
2080  */
2081 static
2083  SCIP* scip, /**< SCIP data structure */
2084  SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2085  )
2086 {
2087  SCIP_CONSDATA* consdata;
2088  int v;
2089 
2090  /* conflict analysis can only be applied in solving stage and if it is applicable */
2092  return SCIP_OKAY;
2093 
2094  consdata = SCIPconsGetData(cons);
2095  assert(consdata != NULL);
2096  assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
2097  || consdata->setppctype == SCIP_SETPPCTYPE_COVERING); /*lint !e641*/
2098 
2099  /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2101 
2102  for( v = 0; v < consdata->nvars; ++v )
2103  {
2104  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
2105  }
2106 
2107  /* analyze the conflict */
2108  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
2109 
2110  return SCIP_OKAY;
2111 }
2112 
2113 /** analyzes conflicting assignment on given constraint where two of the variables where assigned to one,
2114  * and adds conflict constraint to problem
2115  */
2116 static
2118  SCIP* scip, /**< SCIP data structure */
2119  SCIP_CONS* cons /**< set partitioning / packing / covering constraint that detected the conflict */
2120  )
2121 {
2122  SCIP_CONSDATA* consdata;
2123  int v;
2124  int n;
2126  /* conflict analysis can only be applied in solving stage and if it is applicable */
2128  return SCIP_OKAY;
2129 
2130  consdata = SCIPconsGetData(cons);
2131  assert(consdata != NULL);
2132  assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING
2133  || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
2134 
2135  /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
2137 
2138  n = 0;
2139  for( v = 0; v < consdata->nvars && n < 2; ++v )
2140  {
2141  if( SCIPvarGetLbLocal(consdata->vars[v]) > 0.5 )
2142  {
2143  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
2144  n++;
2145  }
2146  }
2147  assert(n == 2);
2148 
2149  /* analyze the conflict */
2150  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
2151 
2152  return SCIP_OKAY;
2153 }
2154 
2155 /** checks constraint for violation only looking at the fixed variables, applies further fixings if possible */
2156 static
2158  SCIP* scip, /**< SCIP data structure */
2159  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint to be processed */
2160  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2161  int* nfixedvars, /**< pointer to count number of deleted variables */
2162  SCIP_Bool* addcut, /**< pointer to store whether this constraint must be added as a cut */
2163  SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
2164  )
2166  SCIP_CONSDATA* consdata;
2167 #ifndef NDEBUG
2168  int oldnfixedvars;
2169 #endif
2170 
2171  assert(cons != NULL);
2172  assert(SCIPconsGetHdlr(cons) != NULL);
2173  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
2174  assert(cutoff != NULL);
2175  assert(nfixedvars != NULL);
2176  assert(addcut != NULL);
2177  assert(mustcheck != NULL);
2178 
2179 #ifndef NDEBUG
2180  oldnfixedvars = *nfixedvars;
2181 #endif
2182 
2183  consdata = SCIPconsGetData(cons);
2184  assert(consdata != NULL);
2185  assert(consdata->nvars == 0 || consdata->vars != NULL);
2186  assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nvars);
2187  assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nvars);
2188 
2189  *addcut = FALSE;
2190  *mustcheck = TRUE;
2191 
2192  /*SCIPdebugMsg(scip, "processing constraint <%s> with respect to fixed variables (%d fixed to 0.0, %d fixed to 1.0)\n",
2193  SCIPconsGetName(cons), consdata->nfixedzeros, consdata->nfixedones);*/
2194 
2195  if( consdata->nfixedones == 1 )
2196  {
2197  /* exactly one variable is fixed to 1:
2198  * - a set covering constraint is feasible anyway and can be disabled
2199  * - all other variables in a set partitioning or packing constraint must be zero
2200  */
2201  if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
2202  {
2203  SCIPdebugMsg(scip, " -> disabling set covering constraint <%s>\n", SCIPconsGetName(cons));
2204  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
2205  }
2206  else
2207  {
2208  if( consdata->nfixedzeros < consdata->nvars - 1 )
2209  {
2210  SCIP_VAR** vars;
2211  SCIP_VAR* var;
2212 #ifndef NDEBUG
2213  SCIP_Bool fixedonefound;
2214 #endif
2215  SCIP_Bool infeasible;
2216  SCIP_Bool tightened;
2217  int nvars;
2218  int v;
2219  int oneidx = -1;
2220 
2221  SCIPdebugMsg(scip, " -> fixing all other variables to zero in set packing/partitioning constraint <%s>\n",
2222  SCIPconsGetName(cons));
2223 
2224  /* unfixed variables exist: fix them to zero;
2225  * this could result in additional variables fixed to one due to aggregations; in this case, the
2226  * constraint is infeasible in local bounds
2227  */
2228  vars = consdata->vars;
2229  nvars = consdata->nvars;
2230 #ifndef NDEBUG
2231  fixedonefound = FALSE;
2232 #endif
2233  for( v = 0; v < nvars && consdata->nfixedones == 1; ++v )
2234  {
2235  var = vars[v];
2236  assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2237  if( SCIPvarGetLbLocal(var) < 0.5 )
2238  {
2239  SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, oneidx, &infeasible, &tightened) );
2240  assert(!infeasible);
2241 
2242  if( tightened )
2243  ++(*nfixedvars);
2244 
2245  SCIPdebugMsg(scip, " -> fixed <%s> to zero (tightened=%u)\n", SCIPvarGetName(var), tightened);
2246  }
2247  else
2248  {
2249 #ifndef NDEBUG
2250  fixedonefound = TRUE;
2251 #endif
2252  oneidx = v;
2253  }
2254  }
2255  /* the fixed to one variable must have been found, and at least one variable must have been fixed */
2256  assert(consdata->nfixedones >= 2 || (fixedonefound && *nfixedvars > oldnfixedvars));
2257 
2258  SCIP_CALL( SCIPresetConsAge(scip, cons) );
2259  }
2260 
2261  /* now all other variables are fixed to zero:
2262  * the constraint is feasible, and if it's not modifiable, it is redundant
2263  */
2264  if( !SCIPconsIsModifiable(cons) && consdata->nfixedones == 1 )
2265  {
2266  SCIPdebugMsg(scip, " -> disabling set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2267  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
2268  }
2269  }
2270  *mustcheck = FALSE;
2271  }
2272 
2273  if( consdata->nfixedones >= 2 )
2274  {
2275  /* at least two variables are fixed to 1:
2276  * - a set covering constraint is feasible anyway and can be disabled
2277  * - a set partitioning or packing constraint is infeasible
2278  */
2279  if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
2280  {
2281  SCIPdebugMsg(scip, " -> disabling set covering constraint <%s>\n", SCIPconsGetName(cons));
2282  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
2283  }
2284  else
2285  {
2286  SCIPdebugMsg(scip, " -> conflict on set packing/partitioning constraint <%s>\n", SCIPconsGetName(cons));
2287 
2288  SCIP_CALL( SCIPresetConsAge(scip, cons) );
2289 
2290  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
2291  SCIP_CALL( analyzeConflictOne(scip, cons) );
2292 
2293  *cutoff = TRUE;
2294  }
2295  *mustcheck = FALSE;
2296  }
2297  else if( consdata->nfixedzeros == consdata->nvars )
2298  {
2299  /* all variables are fixed to zero:
2300  * - a set packing constraint is feasible anyway, and if it's unmodifiable, it can be disabled
2301  * - a set partitioning or covering constraint is infeasible, and if it's unmodifiable, the node
2302  * can be cut off -- otherwise, the constraint must be added as a cut and further pricing must
2303  * be performed
2304  */
2305  assert(consdata->nfixedones == 0);
2306 
2307  if( consdata->setppctype == SCIP_SETPPCTYPE_PACKING ) /*lint !e641*/
2308  {
2309  if( !SCIPconsIsModifiable(cons) )
2310  {
2311  SCIPdebugMsg(scip, " -> disabling set packing constraint <%s>\n", SCIPconsGetName(cons));
2312  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
2313  }
2314  }
2315  else
2316  {
2317  SCIPdebugMsg(scip, " -> set covering/partitioning constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2318 
2319  SCIP_CALL( SCIPresetConsAge(scip, cons) );
2320  if( SCIPconsIsModifiable(cons) )
2321  *addcut = TRUE;
2322  else
2323  {
2324  /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
2325  SCIP_CALL( analyzeConflictZero(scip, cons) );
2326 
2327  *cutoff = TRUE;
2328  }
2329  }
2330  *mustcheck = FALSE;
2331  }
2332  else if( consdata->nfixedzeros == consdata->nvars - 1 && consdata->nfixedones == 0 )
2333  {
2334  /* all variables except one are fixed to zero:
2335  * - a set packing constraint is feasible anyway, and if it's unmodifiable, it can be disabled
2336  * - an unmodifiable set partitioning or covering constraint is feasible and can be disabled after the
2337  * remaining variable is fixed to one
2338  * - a modifiable set partitioning or covering constraint must be checked manually
2339  */
2340  if( consdata->setppctype == SCIP_SETPPCTYPE_PACKING ) /*lint !e641*/
2341  {
2342  if( !SCIPconsIsModifiable(cons) )
2343  {
2344  SCIPdebugMsg(scip, " -> disabling set packing constraint <%s>\n", SCIPconsGetName(cons));
2345  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
2346  }
2347  *mustcheck = FALSE;
2348  }
2349  else if( !SCIPconsIsModifiable(cons) )
2350  {
2351  SCIP_VAR** vars;
2352  SCIP_VAR* var;
2353  SCIP_Bool infeasible;
2354  SCIP_Bool tightened;
2355  int nvars;
2356  int v;
2357 
2358  /* search the single variable that can be fixed */
2359  vars = consdata->vars;
2360  nvars = consdata->nvars;
2361  for( v = 0; v < nvars; ++v )
2362  {
2363  var = vars[v];
2364  assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)));
2365  assert(SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), 1.0));
2366  if( SCIPvarGetUbLocal(var) > 0.5 )
2367  {
2368  SCIPdebugMsg(scip, " -> fixing remaining variable <%s> to one in set covering/partitioning constraint <%s>\n",
2369  SCIPvarGetName(var), SCIPconsGetName(cons));
2370  SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, 0, &infeasible, &tightened) );
2371  assert(!infeasible);
2372  assert(tightened);
2373 
2374  ++(*nfixedvars);
2375  break;
2376  }
2377  }
2378  assert(v < nvars);
2379  assert(consdata->nfixedzeros == consdata->nvars - 1);
2380  assert(consdata->nfixedones == 1);
2381 
2382  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
2383  *mustcheck = FALSE;
2384  }
2385  }
2386  assert(consdata->nfixedzeros + consdata->nfixedones <= consdata->nvars);
2387 
2388  return SCIP_OKAY;
2389 }
2390 
2391 /** checks constraint for violation, returns TRUE iff constraint is feasible */
2392 static
2394  SCIP* scip, /**< SCIP data structure */
2395  SCIP_CONSDATA* consdata, /**< set partitioning / packing / covering constraint to be checked */
2396  SCIP_SOL* sol /**< primal CIP solution */
2397  )
2398 {
2399  SCIP_VAR** vars;
2400  SCIP_Real solval;
2402  SCIP_Real sumbound;
2403  SCIP_Real absviol;
2404  SCIP_Real relviol;
2405  SCIP_Bool check;
2406  int nvars;
2407  int v;
2408 
2409  /* calculate the constraint's activity */
2410  vars = consdata->vars;
2411  nvars = consdata->nvars;
2412  sum = 0.0;
2413  sumbound = ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING ? 1.0 : 1.0 + 2*SCIPfeastol(scip));
2414  for( v = 0; v < nvars && sum < sumbound; ++v ) /* if sum >= sumbound, the feasibility is clearly decided */
2415  {
2416  assert(SCIPvarIsBinary(vars[v]));
2417 
2418  solval = SCIPgetSolVal(scip, sol, vars[v]);
2419  assert(SCIPisFeasGE(scip, solval, 0.0) && SCIPisFeasLE(scip, solval, 1.0));
2420 
2421  sum += solval;
2422  }
2423 
2424  absviol = sum - 1.0;
2425  relviol = SCIPrelDiff(sum, 1.0);
2426  switch( consdata->setppctype )
2427  {
2429  /* in case of partitioning, the violation is equal to the absolute difference between sum and 1 */
2430  absviol = REALABS(absviol);
2431  relviol = REALABS(relviol);
2432  check = SCIPisFeasEQ(scip, sum, 1.0);
2433  break;
2435  /* in case of packing, the violation is equal to how much sum exceeds 1 */
2436  check = SCIPisFeasLE(scip, sum, 1.0);
2437  break;
2439  /* in case of covering, the violation is equal to how much 1 exceeds sum */
2440  absviol = -absviol;
2441  relviol = -relviol;
2442  check = SCIPisFeasGE(scip, sum, 1.0);
2443  break;
2444  default:
2445  SCIPerrorMessage("unknown setppc type\n");
2446  SCIPABORT();
2447  return FALSE; /*lint !e527*/
2448  }
2449 
2450  if( sol != NULL )
2451  SCIPupdateSolLPConsViolation(scip, sol, absviol, relviol);
2452 
2453  return check;
2454 }
2455 
2456 /** creates an LP row in a set partitioning / packing / covering constraint data object */
2457 static
2459  SCIP* scip, /**< SCIP data structure */
2460  SCIP_CONS* cons /**< set partitioning / packing / covering constraint */
2461  )
2462 {
2463  SCIP_CONSDATA* consdata;
2464  SCIP_Real lhs;
2465  SCIP_Real rhs;
2467  consdata = SCIPconsGetData(cons);
2468  assert(consdata != NULL);
2469  assert(consdata->row == NULL);
2470 
2471  switch( consdata->setppctype )
2472  {
2474  lhs = 1.0;
2475  rhs = 1.0;
2476  break;
2478  lhs = -SCIPinfinity(scip);
2479  rhs = 1.0;
2480  break;
2482  lhs = 1.0;
2483  rhs = SCIPinfinity(scip);
2484  break;
2485  default:
2486  SCIPerrorMessage("unknown setppc type\n");
2487  return SCIP_INVALIDDATA;
2488  }
2489 
2490  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row, cons, SCIPconsGetName(cons), lhs, rhs,
2492 
2493  SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row, consdata->nvars, consdata->vars, 1.0) );
2494 
2495  return SCIP_OKAY;
2496 }
2497 
2498 /** adds setppc constraint as cut to the LP */
2499 static
2501  SCIP* scip, /**< SCIP data structure */
2502  SCIP_CONS* cons, /**< setppc constraint */
2503  SCIP_Bool* cutoff /**< whether a cutoff has been detected */
2504  )
2505 {
2506  SCIP_CONSDATA* consdata;
2507 
2508  assert( cutoff != NULL );
2509  *cutoff = FALSE;
2510 
2511  consdata = SCIPconsGetData(cons);
2512  assert(consdata != NULL);
2513 
2514  if( consdata->row == NULL )
2515  {
2516  /* convert set partitioning constraint data into LP row */
2517  SCIP_CALL( createRow(scip, cons) );
2518  }
2519  assert(consdata->row != NULL);
2520 
2521  /* insert LP row as cut */
2522  if( !SCIProwIsInLP(consdata->row) )
2523  {
2524  SCIPdebugMsg(scip, "adding constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
2525  SCIP_CALL( SCIPaddRow(scip, consdata->row, FALSE, cutoff) );
2526  }
2527 
2528  return SCIP_OKAY;
2529 }
2530 
2531 /** adds setppc constraint as row to the NLP, if not added yet */
2532 static
2534  SCIP* scip, /**< SCIP data structure */
2535  SCIP_CONS* cons /**< setppc constraint */
2536  )
2537 {
2538  SCIP_CONSDATA* consdata;
2539 
2540  assert(SCIPisNLPConstructed(scip));
2542  /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
2543  if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) )
2544  return SCIP_OKAY;
2545 
2546  consdata = SCIPconsGetData(cons);
2547  assert(consdata != NULL);
2548 
2549  if( consdata->nlrow == NULL )
2550  {
2551  SCIP_Real lhs, rhs;
2552  SCIP_Real* coefs;
2553  int i;
2554 
2555  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, consdata->nvars) );
2556  for( i = 0; i < consdata->nvars; ++i )
2557  coefs[i] = 1.0;
2558 
2559  switch( SCIPgetTypeSetppc(scip, cons) )
2560  {
2562  lhs = 1.0;
2563  rhs = 1.0;
2564  break;
2565 
2567  lhs = -SCIPinfinity(scip);
2568  rhs = 1.0;
2569  break;
2570 
2572  lhs = 1.0;
2573  rhs = SCIPinfinity(scip);
2574  break;
2575 
2576  default:
2577  SCIPerrorMessage("unexpected setppc type\n");
2578  return SCIP_ERROR;
2579  }
2580 
2581  SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow, SCIPconsGetName(cons),
2582  0.0, consdata->nvars, consdata->vars, coefs, NULL, lhs, rhs, SCIP_EXPRCURV_LINEAR) );
2583  assert(consdata->nlrow != NULL);
2584 
2585  SCIPfreeBufferArray(scip, &coefs);
2586  }
2587 
2588  if( !SCIPnlrowIsInNLP(consdata->nlrow) )
2589  {
2590  SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow) );
2591  }
2592 
2593  return SCIP_OKAY;
2594 }
2595 
2596 /** checks constraint for violation, and adds it as a cut if possible */
2597 static
2599  SCIP* scip, /**< SCIP data structure */
2600  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint to be separated */
2601  SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
2602  SCIP_Bool lpfeas, /**< is the given solution feasible for the current LP ? */
2603  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2604  SCIP_Bool* separated, /**< pointer to store TRUE, if a cut was found */
2605  SCIP_Bool* reduceddom /**< pointer to store TRUE, if a domain reduction was found */
2606  )
2607 {
2608  SCIP_CONSDATA* consdata;
2609  SCIP_Bool addcut;
2610  SCIP_Bool mustcheck;
2611 
2612  assert(cons != NULL);
2613  assert(SCIPconsGetHdlr(cons) != NULL);
2614  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
2615  assert(cutoff != NULL);
2616  assert(separated != NULL);
2617  assert(reduceddom != NULL);
2618 
2619  *cutoff = FALSE;
2620 
2621  consdata = SCIPconsGetData(cons);
2622  assert(consdata != NULL);
2623  assert(consdata->nvars == 0 || consdata->vars != NULL);
2624  assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nvars);
2625  assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nvars);
2626 
2627  /* skip constraints already in the LP */
2628  if( lpfeas && consdata->row != NULL && SCIProwIsInLP(consdata->row) )
2629  return SCIP_OKAY;
2630 
2631  SCIPdebugMsg(scip, "separating constraint <%s>\n", SCIPconsGetName(cons));
2632 
2633  /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2634  if( lpfeas )
2635  {
2636  int nfixedvars = 0;
2637 
2638  SCIP_CALL( processFixings(scip, cons, cutoff, &nfixedvars, &addcut, &mustcheck) );
2639 
2640  *reduceddom = (nfixedvars > 0);
2641  }
2642  else
2643  {
2644  mustcheck = TRUE;
2645  addcut = FALSE;
2646  }
2647 
2648  if( mustcheck )
2649  {
2650  assert(!addcut);
2651 
2652  /* variable's fixings didn't give us any information -> we have to check the constraint */
2653  if( lpfeas && consdata->row != NULL )
2654  {
2655  SCIP_Real feasibility;
2656 
2657  assert(!SCIProwIsInLP(consdata->row));
2658  feasibility = SCIPgetRowSolFeasibility(scip, consdata->row, sol);
2659  addcut = SCIPisFeasNegative(scip, feasibility);
2660  }
2661  else
2662  addcut = !checkCons(scip, consdata, sol);
2663 
2664  if( !addcut )
2665  {
2666  /* constraint was feasible -> increase age */
2667  SCIP_CALL( SCIPincConsAge(scip, cons) );
2668  }
2669  }
2670 
2671  if( addcut )
2672  {
2673  /* insert LP row as cut */
2674  SCIP_CALL( addCut(scip, cons, cutoff) );
2675  SCIP_CALL( SCIPresetConsAge(scip, cons) );
2676  *separated = TRUE;
2677  }
2678 
2679  return SCIP_OKAY;
2680 }
2681 
2682 /** enforces the pseudo solution on the given constraint */
2683 static
2685  SCIP* scip, /**< SCIP data structure */
2686  SCIP_CONS* cons, /**< set partitioning / packing / covering constraint to be separated */
2687  SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2688  SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
2689  SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
2690  SCIP_Bool* solvelp /**< pointer to store TRUE, if the LP has to be solved */
2691  )
2693  SCIP_Bool addcut;
2694  SCIP_Bool mustcheck;
2695  int nfixedvars = 0;
2696 
2697  assert(!SCIPhasCurrentNodeLP(scip));
2698  assert(cons != NULL);
2699  assert(SCIPconsGetHdlr(cons) != NULL);
2700  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
2701  assert(cutoff != NULL);
2702  assert(infeasible != NULL);
2703  assert(reduceddom != NULL);
2704  assert(solvelp != NULL);
2705 
2706  /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
2707  SCIP_CALL( processFixings(scip, cons, cutoff, &nfixedvars, &addcut, &mustcheck) );
2708 
2709  *reduceddom = (nfixedvars > 0);
2710 
2711  if( mustcheck )
2712  {
2713  SCIP_CONSDATA* consdata;
2714 
2715  assert(!addcut);
2716 
2717  consdata = SCIPconsGetData(cons);
2718  assert(consdata != NULL);
2719 
2720  if( checkCons(scip, consdata, NULL) )
2721  {
2722  /* constraint was feasible -> increase age */
2723  SCIP_CALL( SCIPincConsAge(scip, cons) );
2724  }
2725  else
2726  {
2727  /* constraint was infeasible -> reset age */
2728  SCIP_CALL( SCIPresetConsAge(scip, cons) );
2729  *infeasible = TRUE;
2730  }
2731  }
2732 
2733  if( addcut )
2734  {
2735  /* a cut must be added to the LP -> we have to solve the LP immediately */
2736  SCIP_CALL( SCIPresetConsAge(scip, cons) );
2737  *solvelp = TRUE;
2738  }
2739 
2740  return SCIP_OKAY;
2741 }
2742 
2743 /** gets the key of the given element */
2744 static
2745 SCIP_DECL_HASHGETKEY(hashGetKeySetppccons)
2746 { /*lint --e{715}*/
2747  /* the key is the element itself */
2748  return elem;
2749 }
2750 
2751 /** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
2752 static
2753 SCIP_DECL_HASHKEYEQ(hashKeyEqSetppccons)
2754 {
2755 #ifndef NDEBUG
2756  SCIP* scip;
2757 #endif
2758  SCIP_CONSDATA* consdata1;
2759  SCIP_CONSDATA* consdata2;
2760  SCIP_Bool coefsequal;
2761  int i;
2762 
2763  consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
2764  consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
2765  assert(consdata1->sorted);
2766  assert(consdata2->sorted);
2767 #ifndef NDEBUG
2768  scip = (SCIP*)userptr;
2769  assert(scip != NULL);
2770 #endif
2771 
2772  /* checks trivial case */
2773  if( consdata1->nvars != consdata2->nvars )
2774  return FALSE;
2775 
2776  coefsequal = TRUE;
2777 
2778  for( i = 0; i < consdata1->nvars; ++i )
2779  {
2780  /* tests if variables are equal */
2781  if( consdata1->vars[i] != consdata2->vars[i] )
2782  {
2783  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
2784  SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
2785  coefsequal = FALSE;
2786  break;
2787  }
2788  assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
2789  }
2790 
2791  return coefsequal;
2792 }
2793 
2794 /** returns the hash value of the key */
2795 static
2796 SCIP_DECL_HASHKEYVAL(hashKeyValSetppccons)
2797 {
2798  SCIP_CONSDATA* consdata;
2799  int minidx;
2800  int mididx;
2801  int maxidx;
2802 #ifndef NDEBUG
2803  SCIP* scip;
2805  scip = (SCIP*)userptr;
2806  assert(scip != NULL);
2807 #endif
2808 
2809  consdata = SCIPconsGetData((SCIP_CONS*)key);
2810  assert(consdata != NULL);
2811  assert(consdata->nvars > 0);
2812 
2813  /* sorts the constraints */
2814  consdataSort(consdata);
2815 
2816  minidx = SCIPvarGetIndex(consdata->vars[0]);
2817  mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
2818  maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
2819  assert(minidx >= 0 && minidx <= maxidx);
2820 
2821  return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
2822 }
2823 
2824 /** add extra clique-constraints resulting from a given cliquepartition to SCIP */
2825 static
2827  SCIP*const scip, /**< SCIP data structure */
2828  SCIP_VAR**const binvars, /**< binary variables to create clique constraints */
2829  int const nbinvars, /**< number of binary variables to create clique constraints */
2830  int*const cliquepartition, /**< clique partition of binary variables */
2831  int const ncliques, /**< number of cliques in cliquepartition */
2832  SCIP_CONS**const usefulconss, /**< storage for created constraints */
2833  int*const nusefulconss, /**< pointer to store number of useful created constraints */
2834  int const nrounds, /**< actual presolving round */
2835  int*const nfixedvars, /**< pointer to count number of deleted variables */
2836  int*const naddconss, /**< pointer to count number of added constraints */
2837  int*const ndelconss, /**< pointer to count number of deleted constraints */
2838  int*const nchgcoefs, /**< pointer to count number of deleted coefficients */
2839  SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
2840  )
2841 {
2842  SCIP_CONS* cliquecons;
2843  char name[SCIP_MAXSTRLEN];
2844  int lastclqidx;
2845  int nadded;
2846  int c;
2847  int v;
2848 
2849  assert(scip != NULL);
2850  assert(binvars != NULL || nbinvars == 0);
2851  assert(cliquepartition != NULL || nbinvars == 0);
2852  assert(ncliques >= 0 && ncliques <= nbinvars);
2853  assert(usefulconss != NULL);
2854  assert(nusefulconss != NULL);
2855  assert(nfixedvars != NULL);
2856  assert(naddconss != NULL);
2857  assert(ndelconss != NULL);
2858  assert(nchgcoefs != NULL);
2859  assert(cutoff != NULL);
2860 
2861  /* no given binary variables */
2862  if( nbinvars == 0 || ncliques == 0 )
2863  return SCIP_OKAY;
2864 
2865  assert(binvars != NULL);
2866  assert(cliquepartition != NULL);
2867 
2868  /* no useful clique information */
2869  if( ncliques == nbinvars )
2870  return SCIP_OKAY;
2871 
2872  lastclqidx = 0;
2873 
2874  /* @todo: maybe sort cliques and accordingly the variables so it will be faster to add the constraints */
2875  for( c = 0; c < ncliques - 1; ++c )
2876  {
2877  if( lastclqidx >= cliquepartition[c] )
2878  continue;
2879 
2880  nadded = 0;
2881 
2882  /* name the clique constraint */
2883  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "extra_clq_%d_round_%d", cliquepartition[c], nrounds);
2884  SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 0, NULL,
2886 
2887  /* add variables to clique constraint */
2888  for( v = c; v < nbinvars - 1; ++v )
2889  {
2890  if( cliquepartition[c] == cliquepartition[v] )
2891  {
2892  SCIP_CALL( addCoef(scip, cliquecons, binvars[v]) );
2893  ++nadded;
2894  }
2895  }
2896 
2897  /* @todo: try to find a good value for what are enough variables to create this constraint, maybe at least
2898  * (nmaxvars(over all conss)-nminvars(over all conss))/2 */
2899  if( nadded >= 2 )
2900  {
2901  SCIP_CONSDATA* cliqueconsdata;
2902 
2903  SCIPdebugMsg(scip, " -> adding clique constraint: ");
2904  SCIPdebugPrintCons(scip, cliquecons, NULL);
2905  SCIP_CALL( SCIPaddCons(scip, cliquecons) );
2906  ++(*naddconss);
2907 
2908  /* we only want to consider merged constraints */
2909  SCIP_CALL( mergeMultiples(scip, cliquecons, nfixedvars, ndelconss, nchgcoefs, cutoff) );
2910  if( *cutoff )
2911  {
2912  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2913 
2914  return SCIP_OKAY;
2915  }
2916 
2917  cliqueconsdata = SCIPconsGetData(cliquecons);
2918  assert(cliqueconsdata != NULL);
2919 
2920  /* the artificial constraints could be deleted while merging */
2921  if( !SCIPconsIsDeleted(cliquecons) && nadded - cliqueconsdata->nfixedzeros >= 2 )
2922  {
2923  assert(cliqueconsdata->nfixedones == 0);
2924 
2925  /* save the type and constraint */
2926  usefulconss[*nusefulconss] = cliquecons;
2927  ++(*nusefulconss);
2928  }
2929  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2930  }
2931  else
2932  {
2933  SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2934  }
2935  lastclqidx = cliquepartition[c];
2936  }
2937 
2938  return SCIP_OKAY;
2939 }
2940 
2941 
2942 /** start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
2943  * constraints
2944  */
2945 static
2947  SCIP*const scip, /**< SCIP data structure */
2948  SCIP_CONS**const conss, /**< constraint set */
2949  int const nconss, /**< number of constraints in constraint set */
2950  SCIP_CONS**const usefulconss, /**< storage for created constraints */
2951  int*const nusefulconss, /**< pointer to store number of useful created constraints */
2952  int*const nfixedvars, /**< pointer to count number of deleted variables */
2953  int*const ndelconss, /**< pointer to count number of deleted constraints */
2954  int*const nchgcoefs, /**< pointer to count number of deleted coefficients */
2955  SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
2956  )
2957 {
2958  SCIP_CONS* cons;
2959  SCIP_CONSDATA* consdata;
2960  SCIP_Bool addcut;
2961  SCIP_Bool mustcheck;
2962  int nlocaladdconss = 0;
2963  int c;
2964 
2965  assert(scip != NULL);
2966  assert(conss != NULL || nconss == 0);
2967  assert(usefulconss != NULL);
2968  assert(nusefulconss != NULL);
2969  assert(nfixedvars != NULL);
2970  assert(ndelconss != NULL);
2971  assert(nchgcoefs != NULL);
2972  assert(cutoff != NULL);
2973 
2974  if( nconss == 0 )
2975  return SCIP_OKAY;
2976 
2977  assert(conss != NULL);
2978 
2979  for( c = nconss - 1; c >= 0; --c )
2980  {
2981  cons = conss[c];
2982 
2983  /* we only want to consider constraints with either active or negated of active variables, applyfixings removes
2984  * aggregated and fixed variables to zero, processFixings removes fixings to one but no aggregation
2985  *
2986  * @todo: maybe write a new method for deleting aggregations and all fixings
2987  */
2988  SCIP_CALL( applyFixings(scip, cons, &nlocaladdconss, ndelconss, nfixedvars, cutoff) );
2989  if( *cutoff )
2990  return SCIP_OKAY;
2991 
2992  if( SCIPconsIsDeleted(cons) )
2993  {
2994  /* reset nlocaladdconss and continue */
2995  nlocaladdconss = 0;
2996  continue;
2997  }
2998  assert(nlocaladdconss == 0);
2999 
3000  SCIP_CALL( processFixings(scip, cons, cutoff, nfixedvars, &addcut, &mustcheck) );
3001  if( *cutoff )
3002  return SCIP_OKAY;
3003 
3004  consdata = SCIPconsGetData(cons);
3005  assert(consdata != NULL);
3006 
3007  /* we only want to consider merged constraints */
3008  SCIP_CALL( mergeMultiples(scip, cons, nfixedvars, ndelconss, nchgcoefs, cutoff) );
3009  if( *cutoff )
3010  return SCIP_OKAY;
3011 
3012  if( SCIPconsIsModifiable(cons) || !SCIPconsIsActive(cons) )
3013  continue;
3014 
3015  assert(consdata->nfixedones == 0);
3016 
3017  if( consdata->nvars == 0 )
3018  continue;
3019 
3020  /* @todo: check for covering constraints with only two variables which are equal to a packing constraint with
3021  * negated variables */
3022  if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3023  {
3024  assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
3025 
3026  usefulconss[*nusefulconss] = cons;
3027  ++(*nusefulconss);
3028  }
3029  }
3030 
3031  return SCIP_OKAY; /*lint !e438*/
3032 }
3033 
3034 /** creating all necessary data in array structure, collect all clique constraint variables and occurrences,
3035  * @note works only with merged and active not set-covering constraints
3036  */
3037 static
3039  SCIP*const scip, /**< SCIP data structure */
3040  SCIP_CONS**const usefulconss, /**< clique constraints */
3041  int const nusefulconss, /**< number of clique constraints */
3042  SCIP_VAR**const usefulvars, /**< storage for all found variables */
3043  int*const nusefulvars, /**< pointer to store number of added variables */
3044  SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3045  int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3046  int*const maxnvarconsidx, /**< storage for the maximal number of occurrences of a variable */
3047  int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3048  int*const maxnvars /**< pointer to store maximal number of variables of a constraint */
3049  )
3050 {
3051  SCIP_CONS* cons;
3052  SCIP_CONSDATA* consdata;
3053  int varindex;
3054  int c;
3055  int v;
3056 
3057  assert(scip != NULL);
3058  assert(usefulconss != NULL || nusefulconss == 0);
3059  assert(usefulvars != NULL);
3060  assert(nusefulvars != NULL);
3061  assert(vartoindex != NULL);
3062  assert(varnconss != NULL);
3063  assert(maxnvarconsidx != NULL);
3064  assert(varconsidxs != NULL);
3065  assert(maxnvars != NULL);
3066 
3067  if( nusefulconss == 0 )
3068  return SCIP_OKAY;
3069 
3070  assert(usefulconss != NULL);
3071 
3072  for( c = nusefulconss - 1; c >= 0; --c )
3073  {
3074  cons = usefulconss[c];
3075 
3076  assert(SCIPconsIsActive(cons));
3077 
3078  consdata = SCIPconsGetData(cons);
3079  assert(consdata != NULL);
3080 
3081  /* here we should have no covering constraints anymore and the constraint data should be merged */
3082  assert(consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
3083  assert(consdata->merged);
3084 
3085  /* save maximal number of vars */
3086  if( consdata->nvars > *maxnvars )
3087  *maxnvars = consdata->nvars;
3088 
3089  /* adding variables and information about occurrences to local data structure */
3090  for( v = consdata->nvars - 1; v >= 0; --v )
3091  {
3092  SCIP_VAR* var;
3093 
3094  var = consdata->vars[v];
3095  assert(var != NULL);
3096 
3097  /* don't remember fixed vars */
3098  if( SCIPvarGetLbLocal(var) > 0.5 || SCIPvarGetUbLocal(var) < 0.5 )
3099  continue;
3100 
3101  /* only collect active or negated active variables */
3103 
3104  if( !SCIPhashmapExists(vartoindex, (void*) var) )
3105  {
3106  SCIP_VAR* tmpvar;
3107 
3108  usefulvars[*nusefulvars] = var;
3109  ++(*nusefulvars);
3110  varindex = *nusefulvars;
3111  SCIP_CALL( SCIPhashmapInsertInt(vartoindex, (void*) var, varindex) );
3112 
3113  /* get the maximal number of occurrences of this variable, if this variables */
3114  tmpvar = SCIPvarIsNegated(var) ? SCIPvarGetNegatedVar(var) : var;
3115  maxnvarconsidx[varindex] = SCIPvarGetNLocksDownType(tmpvar, SCIP_LOCKTYPE_MODEL)
3117  SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3118  }
3119  else
3120  {
3121  assert(SCIPhashmapExists(vartoindex, (void*) var));
3122  varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var);
3123  }
3124 
3125  /* the number of occurrences of a variable is not limited by the locks (so maybe we have to increase memory),
3126  * because for examples converted cuts are not check and therefore they have no locks on their variables */
3127  if( varnconss[varindex] == maxnvarconsidx[varindex] )
3128  {
3129  maxnvarconsidx[varindex] = SCIPcalcMemGrowSize(scip, maxnvarconsidx[varindex] + 1);
3130  SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3131  }
3132 
3133  assert(varnconss[varindex] < maxnvarconsidx[varindex]);
3134  /* add the constraint number to the variable list */
3135  varconsidxs[varindex][varnconss[varindex]] = c;
3136  /* increase number of occurrences for variables */
3137  ++(varnconss[varindex]);
3138  }
3139  } /* data structure created */
3140 
3141  return SCIP_OKAY;
3142 }
3143 
3144 /** correct clique data due to an aggregation */
3145 static
3147  SCIP_VAR*const var, /**< variable which appears less */
3148  int const considx, /**< constraint index which to remove */
3149  SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3150  int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3151  int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3152  )
3153 {
3154  int varindex;
3155  int i;
3156 #ifndef NDEBUG
3157  SCIP_Bool found = FALSE;
3158 #endif
3159 
3160  assert(var != NULL);
3161  assert(SCIPvarGetLbLocal(var) < 0.5 && SCIPvarGetUbLocal(var) > 0.5);
3162  assert(considx >= 0);
3163  assert(vartoindex != NULL);
3164  assert(varnconss != NULL);
3165  assert(varconsidxs != NULL);
3166 
3167  assert(SCIPhashmapExists(vartoindex, (void*) var));
3168  varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var);
3169 
3170  /* remove entry of variable at the given position */
3171  for( i = 0; i < varnconss[varindex]; ++i )
3172  {
3173  if( varconsidxs[varindex][i] == considx )
3174  {
3175  varconsidxs[varindex][i] = varconsidxs[varindex][varnconss[varindex] - 1];
3176 #ifndef NDEBUG
3177  found = TRUE;
3178 #endif
3179  --(varnconss[varindex]);
3180  break;
3181  }
3182  }
3183  assert(found);
3184 }
3185 
3186 /* correct local data structure, add constraint entry to variable data */
3187 static
3189  SCIP*const scip, /**< SCIP data structure */
3190  SCIP_VAR*const addvar, /**< variable which was added */
3191  int const considx, /**< constraint index which to add */
3192  SCIP_Bool const maybenew, /**< could be a new variables, a negated of an already existing */
3193  SCIP_VAR**const usefulvars, /**< storage for all found variables */
3194  int*const nusefulvars, /**< pointer to store number of added variables */
3195  SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3196  int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3197  int*const maxnvarconsidx, /**< storage for the maximal number of occurrences of a variable */
3198  int**const varconsidxs /**< storage for constraint indices in which the corresponding variable exists */
3199  )
3200 {
3201  int varindex;
3202 
3203  assert(scip != NULL);
3204  assert(addvar != NULL);
3205  assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);
3206  assert(usefulvars != NULL);
3207  assert(nusefulvars != NULL);
3208  assert(vartoindex != NULL);
3209  assert(varnconss != NULL);
3210  assert(maxnvarconsidx != NULL);
3211  assert(varconsidxs != NULL);
3212 
3213  /* we add the variable to the hashmap if its new */
3214  if( maybenew && !SCIPhashmapExists(vartoindex, (void*) addvar) )
3215  {
3216  assert(SCIPvarIsActive(addvar) || SCIPvarIsNegated(addvar));
3217  assert(SCIPvarGetNegatedVar(addvar) != NULL && SCIPhashmapExists(vartoindex, (void*) SCIPvarGetNegatedVar(addvar)));
3218 
3219  /* @note because we can only have created a negated variable, and we already allocated enough memory for
3220  * all (even not existing) negated variables the usefulvars array should be big enough
3221  */
3222  SCIPsortedvecInsertDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, addvar, nusefulvars, NULL);
3223  varindex = *nusefulvars;
3224  SCIP_CALL( SCIPhashmapInsertInt(vartoindex, (void*) addvar, varindex) );
3225 
3226  assert(varconsidxs[varindex] == NULL);
3227 
3228  maxnvarconsidx[varindex] = 1;
3229  SCIP_CALL( SCIPallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3230  varnconss[varindex] = 0;
3231  }
3232  else
3233  {
3234  varindex = SCIPhashmapGetImageInt(vartoindex, (void*) addvar);
3235 
3236  /* grow the needed memory if we added a variable */
3237  if( varnconss[varindex] == maxnvarconsidx[varindex] )
3238  {
3239  maxnvarconsidx[varindex] = SCIPcalcMemGrowSize(scip, maxnvarconsidx[varindex] + 1);
3240  SCIP_CALL( SCIPreallocBufferArray(scip, &(varconsidxs[varindex]), maxnvarconsidx[varindex]) ); /*lint !e866*/
3241  }
3242  }
3243  assert(varnconss[varindex] < maxnvarconsidx[varindex]);
3244  varconsidxs[varindex][varnconss[varindex]] = considx;
3245 
3246  /* increase number of occurrences for variables */
3247  ++(varnconss[varindex]);
3248 
3249  return SCIP_OKAY;
3250 }
3251 
3252 
3253 /** check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3254  * possible
3255  */
3256 static
3258  SCIP*const scip, /**< SCIP data structure */
3259  SCIP_CONS*const cons, /**< constraint */
3260  SCIP_Bool const aggregate, /**< try to aggregate if possible */
3261  SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3262  * yet; both variables are standing next to each other; or NULL if
3263  * aggregate == TRUE
3264  */
3265  SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3266  * type FALSE means the aggregation is of the form x + y = 1; type TRUE means
3267  * the aggregation is of the form x = y; or NULL if aggregate == TRUE
3268  */
3269  int*const naggregations, /**< pointer to store number of aggregations which are not yet performed;
3270  * or NULL if aggregate == TRUE
3271  */
3272  int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3273  * the value is the size of the array for the aggregation variables which
3274  * are not yet performed; or NULL if aggregate == TRUE
3275  */
3276  int*const nfixedvars, /**< pointer to count number of deleted variables */
3277  int*const naggrvars, /**< pointer to count number of aggregated variables */
3278  int*const ndelconss, /**< pointer to count number of deleted constraints */
3279  SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
3280  )
3281 {
3282  SCIP_CONSDATA* consdata;
3283  SCIP_VAR** vars;
3284  int nvars;
3285  int v;
3286  SCIP_Bool fixed;
3287 
3288  assert(scip != NULL);
3289  assert(cons != NULL);
3290  assert(nfixedvars != NULL);
3291  assert(naggrvars != NULL);
3292  assert(ndelconss != NULL);
3293  assert(cutoff != NULL);
3294 
3295  if( !SCIPconsIsActive(cons) )
3296  return SCIP_OKAY;
3297 
3298  consdata = SCIPconsGetData(cons);
3299  assert(consdata != NULL);
3300 
3301  if( consdata->presolpropagated )
3302  return SCIP_OKAY;
3303 
3304  consdata->presolpropagated = TRUE;
3305 
3306  vars = consdata->vars;
3307  nvars = consdata->nvars;
3308 
3309  /* no variables left */
3310  if( nvars == 0 && !SCIPconsIsModifiable(cons) )
3311  {
3312  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3313  {
3314  SCIPdebugMsg(scip, "empty set-partition/-covering constraint <%s> found -> cutoff\n", SCIPconsGetName(cons));
3315  *cutoff = TRUE;
3316 
3317  return SCIP_OKAY;
3318  }
3319  else
3320  {
3321  assert(consdata->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
3322 
3323  /* delete constraint */
3324  SCIPdebugMsg(scip, " -> deleting constraint <%s>, no variables left\n", SCIPconsGetName(cons));
3325  SCIP_CALL( SCIPdelCons(scip, cons) );
3326  ++(*ndelconss);
3327 
3328  return SCIP_OKAY;
3329  }
3330  }
3331 
3332  /* more then two variables are fixed */
3333  if( consdata->nfixedones > 1 )
3334  {
3335  /* at least two variables are fixed to 1:
3336  * - a set covering constraint is feasible anyway and can be deleted
3337  * - a set partitioning or packing constraint is infeasible
3338  */
3339  if( consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3340  {
3341  /* delete constraint */
3342  SCIPdebugMsg(scip, " -> deleting set-covering constraint <%s>, at least two variables are fixed to 1\n", SCIPconsGetName(cons));
3343  SCIP_CALL( SCIPdelCons(scip, cons) );
3344  ++(*ndelconss);
3345 
3346  return SCIP_OKAY;
3347  }
3348 
3349  SCIPdebugMsg(scip, "set partitioning / packing constraint <%s> is infeasible, %d variables fixed to one\n", SCIPconsGetName(cons), consdata->nfixedones);
3350  *cutoff = TRUE;
3351 
3352  return SCIP_OKAY;
3353  }
3354 
3355  if( consdata->nfixedones == 1 )
3356  {
3357  /* exactly one variable is fixed to 1:
3358  * - a set covering constraint is feasible anyway and can be disabled
3359  * - all other variables in a set partitioning or packing constraint must be zero
3360  */
3361  if( consdata->setppctype != SCIP_SETPPCTYPE_COVERING && consdata->nfixedzeros < nvars - 1 ) /*lint !e641*/
3362  {
3363  assert(vars != NULL);
3364 
3365  for( v = nvars - 1; v >= 0; --v )
3366  {
3367  if( SCIPvarGetLbLocal(vars[v]) + 0.5 < SCIPvarGetUbLocal(vars[v]) )
3368  {
3369  SCIPdebugMsg(scip, "trying to fix <%s> to 0 due to at least one variable is already fixed to 1\n", SCIPvarGetName(vars[v]));
3370 
3371  /* fix all remaining variables to zero, constraint is already feasible or infeasible */
3372  SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
3373  if( *cutoff )
3374  {
3375  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 0\n",
3376  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
3377 
3378  return SCIP_OKAY;
3379  }
3380 
3381  assert(fixed);
3382  ++(*nfixedvars);
3383  }
3384  }
3385  }
3386 
3387  if( !SCIPconsIsModifiable(cons) || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3388  {
3389  /* delete constraint */
3390  SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3391  assert(SCIPconsIsActive(cons));
3392  SCIP_CALL( SCIPdelCons(scip, cons) );
3393  ++(*ndelconss);
3394  }
3395 
3396  return SCIP_OKAY;
3397  }
3398 
3399  /* other propagations can only be done on not modifiable constraints */
3400  if( SCIPconsIsModifiable(cons) )
3401  return SCIP_OKAY;
3402 
3403  assert(vars != NULL);
3404 
3405  /* all variables were fixed to zero then either delete the constraint or stop with infeasibility */
3406  if( consdata->nfixedzeros == nvars )
3407  {
3408  assert(consdata->nfixedones == 0);
3409 
3410  /* all variables are fixed to zero:
3411  * - a set packing constraint is feasible anyway and can be deleted
3412  * - a set partitioning or covering constraint is infeasible, and so is the whole problem
3413  */
3414  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3415  {
3416  SCIPdebugMsg(scip, "set partitioning / covering constraint <%s> is infeasible\n", SCIPconsGetName(cons));
3417  *cutoff = TRUE;
3418 
3419  return SCIP_OKAY;
3420  }
3421 
3422  /* delete constraint */
3423  SCIPdebugMsg(scip, " -> deleting set-packing constraint <%s>, all variables are fixed to zero\n", SCIPconsGetName(cons));
3424  assert(SCIPconsIsActive(cons));
3425  SCIP_CALL( SCIPdelCons(scip, cons) );
3426  ++(*ndelconss);
3427 
3428  return SCIP_OKAY;
3429  }
3430 
3431  /* all but one variable were fixed to zero then delete the constraint and for setpartition fix the remaining variable to 1 */
3432  if( consdata->nfixedzeros + 1 == nvars )
3433  {
3434  assert(consdata->nfixedones == 0);
3435 
3436  /* all variables except one are fixed to zero:
3437  * - a set packing constraint is feasible anyway, and can be deleted
3438  * - a set partitioning or covering constraint is feasible and can be deleted after the
3439  * remaining variable is fixed to one
3440  */
3441  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || consdata->setppctype == SCIP_SETPPCTYPE_COVERING ) /*lint !e641*/
3442  {
3443  fixed = FALSE;
3444  for( v = nvars - 1; v >= 0; --v )
3445  {
3446  assert(SCIPvarGetLbLocal(vars[v]) < 0.5);
3447  if( SCIPvarGetUbLocal(vars[v]) > 0.5 )
3448  {
3449  SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to it's the last unfixed variable is the set-partitioning/covering constraint\n", SCIPvarGetName(vars[v]));
3450 
3451  /* fix the remaining set partition variable */
3452  SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, cutoff, &fixed) );
3453  if( *cutoff )
3454  {
3455  SCIPdebugMsg(scip, "setppc constraint <%s>: infeasible fixing <%s> == 1\n",
3456  SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
3457 
3458  return SCIP_OKAY;
3459  }
3460 
3461  assert(fixed);
3462  ++(*nfixedvars);
3463  break;
3464  }
3465  }
3466  assert(fixed);
3467  }
3468 
3469  /* delete constraint */
3470  SCIPdebugMsg(scip, " -> deleting constraint <%s>, all %svariables are fixed\n", SCIPconsGetName(cons), consdata->setppctype == (int) SCIP_SETPPCTYPE_PACKING ? "but one " : "");
3471  assert(SCIPconsIsActive(cons));
3472  SCIP_CALL( SCIPdelCons(scip, cons) );
3473  ++(*ndelconss);
3474 
3475  return SCIP_OKAY;
3476  }
3477 
3478  /* all but two variable were fixed to zero in a setpartitioning constraint then delete the constraint and
3479  * aggregate the remaining two variables
3480  */
3481  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros + 2 == nvars ) /*lint !e641*/
3482  {
3483  SCIP_VAR* var;
3484 
3485  var = NULL;
3486  for( v = nvars - 1; v >= 0; --v )
3487  {
3488  assert(SCIPvarGetLbLocal(vars[v]) < 0.5);
3489 
3490  if( SCIPvarGetUbLocal(vars[v]) > 0.5 )
3491  {
3492  if( var == NULL )
3493  var = vars[v];
3494  else
3495  {
3496  SCIP_Bool redundant;
3497  SCIP_Bool aggregated;
3498 #ifdef VARUSES
3499  SCIP_CONSHDLR* conshdlr;
3500  SCIP_CONSHDLRDATA* conshdlrdata;
3501 
3502  /* get event handler and event handler data */
3503  conshdlr = SCIPconsGetHdlr(cons);
3504  assert(conshdlr != NULL);
3505  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3506  assert(conshdlrdata != NULL);
3507 #endif
3508  if( aggregate )
3509  {
3510  SCIPdebugMsg(scip, "trying to aggregate <%s> and <%s> due to they are the last two unfixed variables in the set partitionning constraint <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));
3511 
3512 #ifdef VARUSES
3513  /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
3514  * and increase usage counting again
3515  */
3516  SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var) );
3517  SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, vars[v]) );
3518 #endif
3519 
3520  /* aggregate last remaining variables in the set partitioning constraint */
3521  SCIP_CALL( SCIPaggregateVars(scip, var, vars[v], 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
3522  if( *cutoff )
3523  {
3524  SCIPdebugMsg(scip, "set partitioning constraint <%s>: aggregate <%s> + <%s> == 1\n",
3525  SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetName(vars[v]));
3526 
3527  return SCIP_OKAY;
3528  }
3529 
3530 #ifdef VARUSES
3531  /* increase variable usage counting again */
3532  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var) );
3533  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, vars[v]) );
3534 #endif
3535 
3536  if( aggregated )
3537  ++(*naggrvars);
3538 
3539  if( redundant )
3540  {
3541  /* delete constraint */
3542  SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3543  assert(SCIPconsIsActive(cons));
3544  SCIP_CALL( SCIPdelCons(scip, cons) );
3545  ++(*ndelconss);
3546  }
3547  }
3548  else
3549  {
3550  assert(undoneaggrvars != NULL);
3551  assert(undoneaggrtypes != NULL);
3552  assert(naggregations != NULL);
3553  assert(saggregations != NULL);
3554 
3555  SCIPdebugMsg(scip, "memorize the aggregation of <%s> + <%s> = 1, because they are the last two unfixed variable in the set partitioning constraints <%s>\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]), SCIPconsGetName(cons));
3556 
3557  /* resize the aggregation arrays if necessary */
3558  if( *saggregations == *naggregations )
3559  {
3560  *saggregations = SCIPcalcMemGrowSize(scip, *naggregations + 1);
3561  assert(*saggregations > *naggregations);
3562  SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrtypes, *saggregations) );
3563  SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrvars, 2 * (*saggregations)) );
3564 
3565  /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
3566  BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
3567  }
3568 
3569  /* memorize aggregation variables*/
3570  assert(undoneaggrtypes[*naggregations] == FALSE);
3571  undoneaggrvars[2 * (*naggregations)] = var;
3572  undoneaggrvars[2 * (*naggregations) + 1] = vars[v];
3573  ++(*naggregations);
3574 
3575  if( !SCIPdoNotAggr(scip) )
3576  {
3577  /* delete constraint */
3578  SCIPdebugMsg(scip, " -> deleting constraint <%s>, all variables are fixed\n", SCIPconsGetName(cons));
3579  assert(SCIPconsIsActive(cons));
3580  SCIP_CALL( SCIPdelCons(scip, cons) );
3581  ++(*ndelconss);
3582  }
3583  }
3584 
3585  return SCIP_OKAY;
3586  }
3587  }
3588  }
3589  /* we should never be here, because the last to unfixed variables should have been either aggregated or a cutoff
3590  * should be applied
3591  */
3592  assert(FALSE); /*lint !e506*/
3593  }
3594 
3595  return SCIP_OKAY;
3596 }
3597 
3598 /** check for overlapping constraint */
3599 static
3601  SCIP*const scip, /**< SCIP data structure */
3602  SCIP_CONS*const cons, /**< constraint which may overlap */
3603  int const considx, /**< constraint index to avoid checking against itself */
3604  int const endidx, /**< end index to check against given constraint */
3605  SCIP_CONS**const usefulconss, /**< clique constraints */
3606  int const nusefulconss, /**< number of clique constraints */
3607  SCIP_VAR**const usefulvars, /**< storage for all found variables */
3608  int*const nusefulvars, /**< pointer to store number of added variables */
3609  SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
3610  int*const varnconss, /**< storage for remembering the number of constraints a variable occurs */
3611  int*const maxnvarconsidx, /**< storage for the maximal number of occurrences of a variable */
3612  int**const varconsidxs, /**< storage for constraint indices in which the corresponding variable exists */
3613  int*const countofoverlapping, /**< the amount of variables of cons which overlap in all other constraint */
3614  SCIP_Bool const shrinking, /**< try to replace some variables with one variable */
3615  SCIP_Bool*const chgcons, /**< pointer to store if the given constraint was changed, due to
3616  * added/deleted variables
3617  */
3618  SCIP_VAR** undoneaggrvars, /**< array to store aggregation variables, if aggregation is not performed
3619  * yet; both variables are standing next to each other;
3620  */
3621  SCIP_Bool* undoneaggrtypes, /**< array to store aggregation type, if aggregation is not performed yet;
3622  * type FALSE means the aggregation is of the form x + y = 1; type TRUE means
3623  * the aggregation is of the form x = y;
3624  */
3625  int*const naggregations, /**< pointer to store number of aggregations which are not yet performed; */
3626  int*const saggregations, /**< pointer to store size of the array for aggregation type and two times
3627  * the value is the size of the array for the aggregation variables which
3628  * are not yet performed;
3629  */
3630  int*const nfixedvars, /**< pointer to count number of deleted variables */
3631  int*const naggrvars, /**< pointer to count number of aggregated variables */
3632  int*const nchgcoefs, /**< pointer to count number of changed coefficients */
3633  int*const ndelconss, /**< pointer to count number of deleted constraints */
3634  SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
3635  )
3636 {
3637  SCIP_CONS* cons1;
3638  SCIP_CONSDATA* consdata1;
3639  SCIP_CONSDATA* consdata;
3640  SCIP_VAR** vars;
3641  SCIP_VAR** vars1;
3642  SCIP_VAR* var;
3643  SCIP_VAR* var1;
3644  SCIP_Bool fixed;
3645  SCIP_Bool overlapdestroyed;
3646  int nvars;
3647  int nvars1;
3648  int oldnfixedzeros;
3649  int c;
3650  int v;
3651  int v1;
3652 #ifndef NDEBUG
3653  int oldnaggrvars;
3654 #endif
3655 
3656  assert(scip != NULL);
3657  assert(cons != NULL);
3658  assert(usefulconss != NULL && nusefulconss > 0);
3659  assert(0 <= considx && considx < nusefulconss);
3660  assert(usefulconss[considx] == cons);
3661  assert(0 <= endidx && endidx <= nusefulconss);
3662  assert(countofoverlapping != NULL);
3663  assert(chgcons != NULL);
3664  assert(undoneaggrvars != NULL);
3665  assert(undoneaggrtypes != NULL);
3666  assert(naggregations != NULL);
3667  assert(saggregations != NULL);
3668  assert(nfixedvars != NULL);
3669  assert(naggrvars != NULL);
3670  assert(nchgcoefs != NULL);
3671  assert(ndelconss != NULL);
3672  assert(cutoff != NULL);
3673 
3674  if( !SCIPconsIsActive(cons) )
3675  return SCIP_OKAY;
3676 
3677  consdata = SCIPconsGetData(cons);
3678  assert(consdata != NULL);
3679 
3680  nvars = consdata->nvars;
3681 
3682  if( nvars == 0 )
3683  return SCIP_OKAY;
3684 
3685  vars = consdata->vars;
3686  assert(vars != NULL);
3687 
3688  oldnfixedzeros = consdata->nfixedzeros;
3689  overlapdestroyed = FALSE;
3690 
3691  /* first check for redundancy for all unprocessed constraints with cons */
3692  for( c = endidx - 1; c >= 0; --c )
3693  {
3694  cons1 = usefulconss[c];
3695 
3696  if( !SCIPconsIsActive(cons1) )
3697  continue;
3698 
3699  /* avoid checking constraint against itself */
3700  if( considx == c )
3701  continue;
3702 
3703  assert(usefulconss[c] != cons);
3704 
3705 #ifndef NDEBUG
3706  oldnaggrvars = *naggrvars;
3707 #endif
3708 
3709  /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
3710  * possible
3711  */
3712  SCIP_CALL( presolvePropagateCons(scip, cons1, FALSE, undoneaggrvars, undoneaggrtypes, naggregations, saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
3713 
3714  if( *cutoff )
3715  return SCIP_OKAY;
3716 
3717  /* we can't handle aggregated variables later on so we should have saved them for later */
3718  assert(*naggrvars == oldnaggrvars);
3719 
3720  if( !SCIPconsIsActive(cons1) )
3721  continue;
3722 
3723  consdata1 = SCIPconsGetData(cons1);
3724  assert(consdata1 != NULL);
3725 
3726  nvars1 = consdata1->nvars;
3727 
3728  if( nvars1 == 0 )
3729  continue;
3730 
3731  /* no more variables from cons as nvars1 can overlap */
3732  assert(countofoverlapping[c] <= nvars1);
3733 
3734  /* constraint should not be redundant or infeasible */
3735  assert(consdata1->nfixedones == 0);
3736 
3737  SCIPdebugMsg(scip, "constraint <%s> overlaps with constraint <%s> by %d variables\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), countofoverlapping[c]);
3738 
3739  /* cons1 includes cons */
3740  if( !overlapdestroyed && countofoverlapping[c] == nvars - consdata->nfixedzeros )
3741  {
3742  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
3743  {
3744  if( nvars - consdata->nfixedzeros < nvars1 )
3745  {
3746 #ifndef NDEBUG
3747  SCIP_Bool negated0;
3748  SCIP_Bool negated1;
3749 #endif
3750 
3751  /* both constraints should stay merged */
3752  assert(consdata->merged);
3753  assert(consdata1->merged);
3754 
3755  vars1 = consdata1->vars;
3756  assert(vars1 != NULL);
3757 
3758  /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3759  SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
3760  /* standard setppc-sorting now lost */
3761  consdata1->sorted = FALSE;
3762 
3763  /* iterate over the both cliques variables the "same" time */
3764  for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
3765  {
3766  if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
3767  {
3768  --v1;
3769  continue;
3770  }
3771  if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
3772  {
3773  --v;
3774  continue;
3775  }
3776 
3777  /* all variables inside the second clique constraint should be either active or negated of an active one */
3778  assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3779 
3780  /* get not negated variable and clique value in cons */
3781  if( SCIPvarGetStatus(vars[v]) != SCIP_VARSTATUS_NEGATED )
3782  {
3783  var = vars[v];
3784 #ifndef NDEBUG
3785  negated0 = FALSE;
3786 #endif
3787  }
3788  else
3789  {
3790  var = SCIPvarGetNegationVar(vars[v]);
3791 #ifndef NDEBUG
3792  negated0 = TRUE;
3793 #endif
3794  }
3795 
3796  /* get active variable and clique value of next variable */
3797  if( SCIPvarIsActive(vars1[v1]) )
3798  {
3799  var1 = vars1[v1];
3800 #ifndef NDEBUG
3801  negated1 = FALSE;
3802 #endif
3803  }
3804  else
3805  {
3807  var1 = SCIPvarGetNegationVar(vars1[v1]);
3808 #ifndef NDEBUG
3809  negated1 = TRUE;
3810 #endif
3811  }
3812 
3813  /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3814  if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
3815  --v;
3816  /* variable index in the constraint is greater than the other one, so fix this variable */
3817  else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
3818  {
3819  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3820 
3821  /* fix all variables except the one which has the negated var in the clique to zero */
3822  SCIP_CALL( SCIPfixVar(scip, vars1[v1], 0.0, cutoff, &fixed) );
3823  if( *cutoff )
3824  {
3825  SCIPdebugMsg(scip, "fixing led to cutoff\n");
3826 
3827  return SCIP_OKAY;
3828  }
3829 
3830  assert(fixed);
3831  ++(*nfixedvars);
3832  --v1;
3833  }
3834  else
3835  {
3836  /* because the constraint's are merged it is not possible that one constraint contains a negated
3837  * variable of another and because all variables in cons are in cons1 this should be really the
3838  * same variable here; so we can decrease v and v1
3839  */
3840  assert(negated0 == negated1);
3841 
3842  --v;
3843  --v1;
3844  }
3845  }
3846  /* maybe we ended because of cons(v reached -1) so try to add rest of cons1 to cons */
3847  for( ; v1 >= 0; --v1)
3848  {
3849  if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
3850  continue;
3851 
3852  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars1[v1]));
3853 
3854  /* fix all variables except the one which has the negated var in the clique to zero */
3855  SCIP_CALL( SCIPfixVar(scip, vars1[v1], 0.0, cutoff, &fixed) );
3856  if( *cutoff )
3857  {
3858  SCIPdebugMsg(scip, "fixing led to cutoff\n");
3859 
3860  return SCIP_OKAY;
3861  }
3862 
3863  assert(fixed);
3864  ++(*nfixedvars);
3865  }
3866  }
3867 
3868  /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
3869  * fixed to one, it's infeasible */
3870  if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->nfixedzeros == nvars1 && consdata1->nfixedones != 1 ) /*lint !e641*/
3871  {
3872  SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
3873  *cutoff = TRUE;
3874 
3875  return SCIP_OKAY;
3876  }
3877 
3878  assert(SCIPconsIsActive(cons1));
3879  /* delete second constraint */
3880  SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
3881 
3882  SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
3883  SCIP_CALL( SCIPdelCons(scip, cons1) );
3884  ++(*ndelconss);
3885  }
3886  /* could already be deleted because the constraint was included in another set partition constraint */
3887  else if( SCIPconsIsActive(cons) )
3888  {
3889  /* delete cons due to redundancy to cons1 */
3890  SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
3891 
3892  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
3893  SCIP_CALL( SCIPdelCons(scip, cons) );
3894  ++(*ndelconss);
3895  }
3896  }
3897  /* cons includes cons1
3898  *
3899  * @note that zero fixations from above can only appear through a set-partitioning constraint, this means if
3900  * cons was the set-partitioning constraint only variables which are not in this constraint could be fixed
3901  * to zero, and this also means that the overlapping variables in this particular case are still active or
3902  * fixed to 1
3903  * later on it could be possible that even variables in cons are fixed to zero, which can lead to wrong
3904  * results when checking if countofoverlapping[c] + consdata1->nfixedzeros == nvars1, because a fixed
3905  * variable could be counted twice
3906  */
3907  else if( (!overlapdestroyed && countofoverlapping[c] + consdata1->nfixedzeros == nvars1) || countofoverlapping[c] == nvars1 )
3908  {
3909  /* even in deleted constraints we may fix unfixed variables */
3910  if( consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
3911  {
3912  const int oldnfixedvars = *nfixedvars;
3913 #ifndef NDEBUG
3914  SCIP_Bool negated0;
3915  SCIP_Bool negated1;
3916 #endif
3917  /* both constraints should stay merged */
3918  assert(consdata->merged);
3919  assert(consdata1->merged);
3920 
3921  vars1 = consdata1->vars;
3922 
3923  /* sorting array after indices of variables, negated and active counterparts would stand side by side */
3924  SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
3925  /* standard setppc-sorting now lost */
3926  consdata1->sorted = FALSE;
3927 
3928  /* iterate over the both cliques variables the "same" time */
3929  for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
3930  {
3931  if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
3932  {
3933  --v1;
3934  continue;
3935  }
3936  if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
3937  {
3938  --v;
3939  continue;
3940  }
3941 
3942  /* all variables inside the second clique constraint should be either active or negated of an active one */
3943  assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
3944  /* all variables inside the first clique constraint should be either active or negated of an active one */
3945  assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
3946 
3947  /* get not negated variable and clique value in cons */
3948  if( SCIPvarIsActive(vars[v]) )
3949  {
3950  var = vars[v];
3951 #ifndef NDEBUG
3952  negated0 = FALSE;
3953 #endif
3954  }
3955  else
3956  {
3958  var = SCIPvarGetNegationVar(vars[v]);
3959 #ifndef NDEBUG
3960  negated0 = TRUE;
3961 #endif
3962  }
3963 
3964  /* get active variable and clique value of next variable */
3965  if( SCIPvarIsActive(vars1[v1]) )
3966  {
3967  var1 = vars1[v1];
3968 #ifndef NDEBUG
3969  negated1 = FALSE;
3970 #endif
3971  }
3972  else
3973  {
3975  var1 = SCIPvarGetNegationVar(vars1[v1]);
3976 #ifndef NDEBUG
3977  negated1 = TRUE;
3978 #endif
3979  }
3980 
3981  /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
3982  if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
3983  {
3984  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(var));
3985 
3986  /* fix all variables except the one which has the negated var in the clique to zero */
3987  SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
3988  if( *cutoff )
3989  {
3990  SCIPdebugMsg(scip, "fixing led to cutoff\n");
3991 
3992  return SCIP_OKAY;
3993  }
3994 
3995  assert(fixed);
3996  ++(*nfixedvars);
3997 
3998  --v;
3999  }
4000  /* variable index in the constraint is greater than the other one, so fix this variable */
4001  else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4002  --v1;
4003  else
4004  {
4005  /* because the constraint's are merged it is not possible that one constraint contains a negated
4006  * variable of another and because all variables in cons1 are in cons this should be really the same
4007  * variable here; so we can decrease v and v1
4008  */
4009  assert(negated0 == negated1);
4010 
4011  --v;
4012  --v1;
4013  }
4014  }
4015 
4016  /* maybe we ended because of cons1(v1 reached -1) so try to add rest of cons to cons1 */
4017  for( ; v >= 0; --v)
4018  {
4019  if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
4020  continue;
4021 
4022  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because it is in the same clique with a complete set partitioning constraint\n", SCIPvarGetName(vars[v]));
4023 
4024  /* fix all variables except the one which has the negated var in the clique to zero */
4025  SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, cutoff, &fixed) );
4026  if( *cutoff )
4027  {
4028  SCIPdebugMsg(scip, "fixing led to cutoff\n");
4029 
4030  return SCIP_OKAY;
4031  }
4032 
4033  assert(fixed);
4034  ++(*nfixedvars);
4035  }
4036 
4037  /* if caused by all fixings now this set partitioning constraint doesn't have any variable which was
4038  * fixed to one, it's infeasible */
4039  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata->nfixedzeros == nvars && consdata->nfixedones != 1 ) /*lint !e641*/
4040  {
4041  SCIPdebugMsg(scip, "all variables in the set-partitioning constraint <%s> are fixed to zero, this leads to a cutoff\n", SCIPconsGetName(cons1));
4042  *cutoff = TRUE;
4043 
4044  return SCIP_OKAY;
4045  }
4046 
4047  /* could already be deleted because the constraint was included in another set partition constraint */
4048  if( SCIPconsIsActive(cons) )
4049  {
4050  /* delete cons because it include another set partitioning constraint */
4051  SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it includes the setpartitioning constraint <%s> number <%d>\n", SCIPconsGetName(cons), considx, SCIPconsGetName(cons1), c);
4052  assert(SCIPconsIsActive(cons));
4053 
4054  SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons) );
4055  SCIP_CALL( SCIPdelCons(scip, cons) );
4056  ++(*ndelconss);
4057  }
4058 
4059  /* due to fixings in cons0 mark overlapping invalid for checking with fixedzero variables together */
4060  if( oldnfixedvars < *nfixedvars )
4061  overlapdestroyed = TRUE;
4062  }
4063  else
4064  {
4065  assert(consdata1->setppctype == SCIP_SETPPCTYPE_PACKING); /*lint !e641*/
4066 
4067  /* delete cons1 due to redundancy to cons */
4068  SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to inclusion in constraint <%s> number <%d>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons), considx);
4069  assert(SCIPconsIsActive(cons1));
4070 
4071  SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
4072  SCIP_CALL( SCIPdelCons(scip, cons1) );
4073  ++(*ndelconss);
4074  }
4075  }
4076  /* if cons has only one unfixed variable which is not in cons1 and cons1 has one variable which does not appear in
4077  * cons and both constraints are setpartitioning constraints we might aggregate both not overlapping variables and
4078  * delete one constraint
4079  */
4080  else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1 && countofoverlapping[c] == nvars1 - 1 ) /*lint !e641*/
4081  {
4082  SCIP_VAR* aggvar1;
4083  SCIP_VAR* aggvar2;
4084  SCIP_Bool negated0;
4085  SCIP_Bool negated1;
4086 
4087  aggvar1 = NULL;
4088  aggvar2 = NULL;
4089 
4090  /* both constraints should stay merged */
4091  assert(consdata->merged);
4092  assert(consdata1->merged);
4093 
4094  vars1 = consdata1->vars;
4095 
4096  /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4097  SCIPsortDownPtr((void**)vars1, SCIPvarCompActiveAndNegated, nvars1);
4098  /* standard setppc-sorting now lost */
4099  consdata1->sorted = FALSE;
4100 
4101  /* iterate over the both cliques variables the "same" time */
4102  for( v = nvars - 1, v1 = nvars1 - 1; v >= 0 && v1 >= 0; )
4103  {
4104  if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
4105  {
4106  --v1;
4107  continue;
4108  }
4109  if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
4110  {
4111  --v;
4112  continue;
4113  }
4114 
4115  /* all variables inside the second clique constraint should be either active or negated of an active one */
4116  assert(SCIPvarIsActive(vars1[v1]) || (SCIPvarGetStatus(vars1[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars1[v1]))));
4117  /* all variables inside the first clique constraint should be either active or negated of an active one */
4118  assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
4119 
4120  /* get not negated variable and clique value in cons */
4121  if( SCIPvarIsActive(vars[v]) )
4122  {
4123  var = vars[v];
4124  negated0 = FALSE;
4125  }
4126  else
4127  {
4129  var = SCIPvarGetNegationVar(vars[v]);
4130  negated0 = TRUE;
4131  }
4132 
4133  /* get active variable and clique value of next variable */
4134  if( SCIPvarIsActive(vars1[v1]) )
4135  {
4136  var1 = vars1[v1];
4137  negated1 = FALSE;
4138  }
4139  else
4140  {
4142  var1 = SCIPvarGetNegationVar(vars1[v1]);
4143  negated1 = TRUE;
4144  }
4145 
4146  /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4147  if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
4148  {
4149  assert(aggvar1 == NULL);
4150  aggvar1 = vars[v];
4151 
4152  if( aggvar2 != NULL )
4153  break;
4154 
4155  --v;
4156  }
4157  /* variable index in the constraint is greater than the other one, so fix this variable */
4158  else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4159  {
4160  assert(aggvar2 == NULL);
4161  aggvar2 = vars1[v1];
4162 
4163  if( aggvar1 != NULL )
4164  break;
4165 
4166  --v1;
4167  }
4168  else
4169  {
4170  /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4171  * of another, but both variables in both constraints still can be negated to each other
4172  */
4173  if( negated0 != negated1 )
4174  {
4175  /* cons is except for one variable equal to cons1 and the unequal variable in cons is negated
4176  * to the one in cons1, so the problem is infeasible
4177  */
4178  SCIPdebugMsg(scip, "two set-partitioning constraint <%s> and <%s> have only one variable not in common, but this variable <%s> appears in one constraint as the negated version as in the other constraint\n", SCIPconsGetName(cons), SCIPconsGetName(cons1), SCIPvarGetName(vars[v]));
4179  *cutoff = TRUE;
4180 
4181  return SCIP_OKAY;
4182  }
4183  --v;
4184  --v1;
4185  }
4186  }
4187 
4188  /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4189  if( aggvar1 == NULL && aggvar2 == NULL )
4190  continue;
4191 
4192  /* determine second aggregation var, if not yet done */
4193  if( aggvar2 == NULL )
4194  {
4195  for( ; v1 >= 0; --v1)
4196  {
4197  if( SCIPvarGetLbLocal(vars1[v1]) > 0.5 || SCIPvarGetUbLocal(vars1[v1]) < 0.5 )
4198  continue;
4199 
4200  aggvar2 = vars1[v1];
4201  break;
4202  }
4203  }
4204  /* determine first aggregation var, if not yet done */
4205  else if( aggvar1 == NULL )
4206  {
4207  /* maybe we ended because of cons1(v1 reached -1) so find the aggvar1 in cons */
4208  for( ; v >= 0; --v)
4209  {
4210  if( SCIPvarGetLbLocal(vars[v]) > 0.5 || SCIPvarGetUbLocal(vars[v]) < 0.5 )
4211  continue;
4212 
4213  aggvar1 = vars[v];
4214  break;
4215  }
4216  }
4217 
4218  /* due to fixings, it is possible that there are no active variables left, we we did not recognize which variables we could aggregate */
4219  if( aggvar1 == NULL || aggvar2 == NULL )
4220  continue;
4221 
4222  SCIPdebugMsg(scip, "memorize the aggregation of <%s> == <%s>, because they are the last two variable which are different in these two set partitioning constraints <%s> <%s>\n", SCIPvarGetName(aggvar1), SCIPvarGetName(aggvar2), SCIPconsGetName(cons), SCIPconsGetName(cons1));
4223 
4224  /* resize the aggregation arrays if necessary */
4225  if( *saggregations == *naggregations )
4226  {
4227  *saggregations = SCIPcalcMemGrowSize(scip, *naggregations + 1);
4228  assert(*saggregations > *naggregations);
4229  SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrtypes, *saggregations) );
4230  SCIP_CALL( SCIPreallocBufferArray(scip, &undoneaggrvars, 2 * (*saggregations)) );
4231 
4232  /* clear the aggregation type array to set the default to the aggregation of the form x + y = 1 */
4233  BMSclearMemoryArray(&(undoneaggrtypes[*naggregations]), *saggregations - *naggregations); /*lint !e866*/
4234  }
4235 
4236  /* memorize aggregation variables*/
4237  undoneaggrtypes[*naggregations] = TRUE;
4238  undoneaggrvars[2 * (*naggregations)] = aggvar1;
4239  undoneaggrvars[2 * (*naggregations) + 1] = aggvar2;
4240  ++(*naggregations);
4241 
4242  if( !SCIPdoNotAggr(scip) )
4243  {
4244  /* delete constraint */
4245  SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> because it is dominated by constraint <%s>\n", SCIPconsGetName(cons1), c, SCIPconsGetName(cons));
4246  assert(SCIPconsIsActive(cons1));
4247 
4248  SCIP_CALL( SCIPupdateConsFlags(scip, cons, cons1) );
4249  SCIP_CALL( SCIPdelCons(scip, cons1) );
4250  ++(*ndelconss);
4251  }
4252  }
4253  /* w.l.o.g. cons is a setpartitioning constraint and countofoverlapping == nvars - oldnfixedzeros - 1 we can
4254  * delete all overlapping variables in cons1 and add the negated variable of the not overlapped variable to cons
4255  * 1; the result should be a shorter constraint with the same impact
4256  */
4257  else if( shrinking && !overlapdestroyed && countofoverlapping[c] > 1 && ((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) || (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars1 - 1)) ) /*lint !e641*/
4258  {
4259  SCIP_CONSDATA* consdatachange;
4260  SCIP_VAR** varstostay;
4261  SCIP_VAR** varstochange;
4262  SCIP_CONS* constochange;
4263  SCIP_CONS* constostay;
4264  SCIP_VAR* addvar;
4265  SCIP_Bool negated0;
4266  SCIP_Bool negated1;
4267  int nvarstostay;
4268  int nvarstochange;
4269  int constochangeidx;
4270 #ifndef NDEBUG
4271  const int oldnchgcoefs = *nchgcoefs;
4272 #endif
4273 
4274  addvar = NULL;
4275 
4276  assert((consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING) != (consdata1->setppctype == SCIP_SETPPCTYPE_PARTITIONING) || countofoverlapping[c] != nvars - 1 || countofoverlapping[c] != nvars1 - 1); /*lint !e641*/
4277 
4278  /* both constraints should stay merged */
4279  assert(consdata->merged);
4280  assert(consdata1->merged);
4281 
4282  /* sorting array after indices of variables, negated and active counterparts would stand side by side */
4283  SCIPsortDownPtr((void**)(consdata1->vars), SCIPvarCompActiveAndNegated, nvars1);
4284  /* standard setppc-sorting now lost */
4285  consdata1->sorted = FALSE;
4286 
4287  /* initialize variables */
4288  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING && countofoverlapping[c] == nvars - oldnfixedzeros - 1) /*lint !e641*/
4289  {
4290  varstostay = vars;
4291  varstochange = consdata1->vars;
4292  nvarstostay = nvars;
4293  nvarstochange = nvars1;
4294  constostay = cons;
4295  constochange = cons1;
4296  consdatachange = consdata1;
4297  constochangeidx = c;
4298  }
4299  else
4300  {
4301  varstostay = consdata1->vars;
4302  varstochange = vars;
4303  nvarstostay = nvars1;
4304  nvarstochange = nvars;
4305  constostay = cons1;
4306  constochange = cons;
4307  consdatachange = consdata;
4308  constochangeidx = considx;
4309 
4310  *chgcons = TRUE;
4311  }
4312 
4313  /* iterate over the both cliques variables the "same" time, here we need the backward loop, because we
4314  * delete some variables and we don not want to loose order
4315  */
4316  for( v = nvarstostay - 1, v1 = nvarstochange - 1; v >= 0 && v1 >= 0; )
4317  {
4318  if( SCIPvarGetLbLocal(varstochange[v1]) > 0.5 || SCIPvarGetUbLocal(varstochange[v1]) < 0.5 )
4319  {
4320  --v1;
4321  continue;
4322  }
4323  if( SCIPvarGetLbLocal(varstostay[v]) > 0.5 || SCIPvarGetUbLocal(varstostay[v]) < 0.5 )
4324  {
4325  --v;
4326  continue;
4327  }
4328 
4329  /* all variables inside the second clique constraint should be either active or negated of an active one */
4330  assert(SCIPvarIsActive(varstochange[v1]) || (SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1]))));
4331  /* all variables inside the first clique constraint should be either active or negated of an active one */
4332  assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4333 
4334  /* get not negated variable and clique value in constostay */
4335  if( SCIPvarIsActive(varstostay[v]) )
4336  {
4337  var = varstostay[v];
4338  negated0 = FALSE;
4339  }
4340  else
4341  {
4342  assert(SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v])));
4343  var = SCIPvarGetNegationVar(varstostay[v]);
4344  negated0 = TRUE;
4345  }
4346 
4347  /* get active variable and clique value of in constochange*/
4348  if( SCIPvarIsActive(varstochange[v1]) )
4349  {
4350  var1 = varstochange[v1];
4351  negated1 = FALSE;
4352  }
4353  else
4354  {
4355  assert(SCIPvarGetStatus(varstochange[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstochange[v1])));
4356  var1 = SCIPvarGetNegationVar(varstochange[v1]);
4357  negated1 = TRUE;
4358  }
4359 
4360  /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4361  if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
4362  {
4363  assert(addvar == NULL);
4364  addvar = varstostay[v];
4365  --v;
4366  }
4367  /* variable index in the constraint is greater than the other one, so fix this variable */
4368  else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4369  {
4370  --v1;
4371  }
4372  else
4373  {
4374  /* because the constraint's are merged it is not possible that one constraint contains a negated variable
4375  * of another, but both constraint might have a variable in negated form of the other
4376  */
4377  if( negated0 != negated1 )
4378  {
4379  assert(addvar == NULL);
4380 
4381  SCIPdebugMsg(scip, "-> trying to fix <%s> to 0 because it would exist twice in a constraint\n", SCIPvarGetName(varstochange[v1]));
4382 
4383  /* fix variable to zero */
4384  SCIP_CALL( SCIPfixVar(scip, varstochange[v1], 0.0, cutoff, &fixed) );
4385  if( *cutoff )
4386  {
4387  SCIPdebugMsg(scip, "fixing led to cutoff\n");
4388 
4389  return SCIP_OKAY;
4390  }
4391 
4392  assert(fixed);
4393  ++(*nfixedvars);
4394 
4395  /* the above fixing is equal to the fixation of varstostay[v] to 1, so we can call presolvePropagateCons() for consstay */
4396  SCIP_CALL( presolvePropagateCons(scip, constostay, FALSE, NULL, NULL, NULL, NULL, nfixedvars, naggrvars, ndelconss, cutoff) );
4397 
4398  return SCIP_OKAY;
4399  }
4400  else
4401  {
4402  /* correct local data structure, remove variable from constraint entry where it will be removed */
4403  deleteCliqueDataEntry(varstochange[v1], constochangeidx, vartoindex, varnconss, varconsidxs);
4404 
4405  SCIPdebugMsg(scip, " -> deleting variable <%s> in constraint <%s> number %d, because it will be replaced\n", SCIPvarGetName(varstochange[v1]), SCIPconsGetName(constochange), constochangeidx);
4406  /* delete overlapping variables in constochange */
4407  SCIP_CALL( delCoefPos(scip, constochange, v1) );
4408  ++(*nchgcoefs);
4409  }
4410 
4411  --v;
4412  --v1;
4413  }
4414  }
4415  assert(addvar != NULL || v >= 0);
4416  /* we should have removed exactly countofoverlapping[c] variables from the constochange */
4417  assert(*nchgcoefs - oldnchgcoefs == countofoverlapping[c]);
4418 
4419  /* determine addvar if not yet found */
4420  if( addvar == NULL )
4421  {
4422  for( ; v >= 0; --v)
4423  {
4424  if( SCIPvarGetLbLocal(varstostay[v]) > 0.5 || SCIPvarGetUbLocal(varstostay[v]) < 0.5 )
4425  continue;
4426 
4427  /* all variables inside the first clique constraint should be either active or negated of an active one */
4428  assert(SCIPvarIsActive(varstostay[v]) || (SCIPvarGetStatus(varstostay[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(varstostay[v]))));
4429 
4430  addvar = varstostay[v];
4431  break;
4432  }
4433  }
4434  assert(addvar != NULL);
4435 
4436  /* get representative variable for all deleted variables */
4437  SCIP_CALL( SCIPgetNegatedVar(scip, addvar, &addvar) );
4438  assert(addvar != NULL);
4439 
4440  SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(constochange), constochangeidx);
4441  /* add representative for overlapping instead */
4442  SCIP_CALL( addCoef(scip, constochange, addvar) );
4443  ++(*nchgcoefs);
4444 
4445  /* constraint should be still merged because this added variable is new in this constraint */
4446  consdatachange->merged = TRUE;
4447  assert(constochangeidx == (cons == constochange ? considx : c));
4448 
4449  /* correct local data structure, add constraint entry to variable data */
4450  SCIP_CALL( addCliqueDataEntry(scip, addvar, constochangeidx, TRUE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4451 
4452  /* cons changed so much, that it cannot be used for more overlapping checks */
4453  if( *chgcons )
4454  return SCIP_OKAY;
4455  }
4456  }
4457 
4458  return SCIP_OKAY;
4459 }
4460 
4461 /** try to lift variables to given constraint */
4462 /** @todo try another variant by determine lifting variables as the intersection of all cliques variables of the
4463  * constraint variables, note that the intersection changes after one variable was added
4464  */
4465 static
4467  SCIP*const scip, /**< SCIP data structure */
4468  SCIP_CONS*const cons, /**< constraint which may overlap */
4469  int const arraypos, /**< position of constraint in global array */
4470  SCIP_VAR**const usefulvars, /**< possible variables to lift */
4471  int*const nusefulvars, /**< pointer to store number of added variables */
4472  int const endidx, /**< end index for possible lifting variables */
4473  SCIP_Bool** cliquevalues, /**< pointer to clique values of constraint-variables, either one if the
4474  * variable is active or zero if the variable is negated
4475  * @note this array can be resized in this method
4476  */
4477  SCIP_HASHMAP*const vartoindex, /**< hashmap mapping variables to indices */
4478  int*const varnconss, /**< array with number of constraints a variable occurs */
4479  int*const maxnvarconsidx, /**< array with the maximal number of occurrences of a variable */
4480  int**const varconsidxs, /**< array with constraint indices in which the corresponding variable
4481  * exists
4482  */
4483  int*const maxnvars, /**< pointer to store maximal number of variables of a constraint */
4484  int*const nadded, /**< pointer to store number of possible added variables */
4485  SCIP_Bool*const chgcons, /**< pointer to store if the constraint was changed, due to added
4486  * variables
4487  */
4488  int*const nfixedvars, /**< pointer to count number of deleted variables */
4489  int*const ndelconss, /**< pointer to count number of deleted constraints */
4490  SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
4491  )
4492 {
4493  SCIP_CONSDATA* consdata;
4494  SCIP_VAR** vars;
4495  SCIP_VAR* var;
4496  SCIP_VAR* var1;
4497  SCIP_Bool fixed;
4498  SCIP_Bool value;
4499  int nvars;
4500  int nottocheck; /* will be the position for a variable in cons0 which is in negated form in the same clique */
4501  int v;
4502  int v1;
4503  int k;
4504 
4505  assert(scip != NULL);
4506  assert(cons != NULL);
4507  assert(usefulvars != NULL);
4508  assert(cliquevalues != NULL);
4509  assert(*cliquevalues != NULL);
4510  assert(vartoindex != NULL);
4511  assert(varnconss != NULL);
4512  assert(maxnvarconsidx != NULL);
4513  assert(varconsidxs != NULL);
4514  assert(maxnvars != NULL);
4515  assert(nadded != NULL);
4516  assert(chgcons != NULL);
4517  assert(nfixedvars != NULL);
4518  assert(ndelconss != NULL);
4519  assert(cutoff != NULL);
4520 
4521  if( !SCIPconsIsActive(cons) )
4522  return SCIP_OKAY;
4523 
4524  consdata = SCIPconsGetData(cons);
4525  assert(consdata != NULL);
4526 
4527  nvars = consdata->nvars;
4528 
4529  if( nvars == 0 )
4530  return SCIP_OKAY;
4531 
4532  assert(nvars <= *maxnvars);
4533 
4534  vars = consdata->vars;
4535  assert(vars != NULL);
4536 
4537  v1 = endidx;
4538 
4539  /* now we try to add variables with index prior to endidx to cons */
4540  for( v = nvars - 1; v >= 0 && v1 >= 0; )
4541  {
4542  if( SCIPvarGetLbLocal(usefulvars[v1]) > 0.5 || SCIPvarGetUbLocal(usefulvars[v1]) < 0.5 )
4543  {
4544  --v1;
4545  continue;
4546  }
4547  if( SCIPvarGetUbLocal(vars[v]) < 0.5 )
4548  {
4549  --v;
4550  continue;
4551  }
4552 
4553  /* check that constraint variables are still correctly sorted, indices of active variables should be decreasing */
4554  assert(v == 0 || SCIPvarCompareActiveAndNegated(vars[v], vars[v - 1]) <= 0);
4555 
4556  /* there should no variables fixed to one occur in our constraint */
4557  assert(SCIPvarGetLbLocal(vars[v]) < 0.5 && SCIPvarGetUbLocal(vars[v]) > 0.5);
4558  assert(SCIPvarGetLbLocal(usefulvars[v1]) < 0.5 && SCIPvarGetUbLocal(usefulvars[v1]) > 0.5);
4559 
4560  /* all variables which we have inside the clique constraint and which can possibly be added should be either active or negated */
4561  assert(SCIPvarIsActive(vars[v]) || (SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[v]))));
4562  assert(SCIPvarIsActive(usefulvars[v1]) || (SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1]))));
4563 
4564  /* constraint should during adding of variables stay merged, because for each variable which is added holds that
4565  * the index of this corresponding active variable is pairwise different to all indices of all active
4566  * corresponding variables inside the constraint
4567  * @note it should not happen that we add one variable and the corresponding counterpart to the same constraint */
4568  assert(consdata->merged);
4569 
4570  /* get active variable and clique value in cons */
4571  if( (*cliquevalues)[v] )
4572  var = vars[v];
4573  else
4574  {
4576  var = SCIPvarGetNegationVar(vars[v]);
4577  }
4578 
4579  /* get active variable and clique value of next variable */
4580  if( SCIPvarIsActive(usefulvars[v1]) )
4581  {
4582  var1 = usefulvars[v1];
4583  value = TRUE;
4584  }
4585  else
4586  {
4587  assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4588  var1 = SCIPvarGetNegationVar(usefulvars[v1]);
4589  value = FALSE;
4590  }
4591 
4592  nottocheck = -1;
4593  k = 0;
4594 
4595  /* variable index in the constraint smaller than the other one, so go to the next variable in cons */
4596  if( SCIPvarGetIndex(var) < SCIPvarGetIndex(var1) )
4597  {
4598  --v;
4599  continue;
4600  }
4601  /* variable index in the constraint is greater than the other one, so check for possible inclusion of the variable */
4602  else if( SCIPvarGetIndex(var) > SCIPvarGetIndex(var1) )
4603  {
4604  assert(consdata == SCIPconsGetData(cons));
4605 
4606  /* check if every variable in the actual clique is in clique with the new variable */
4607  for( k = nvars - 1; k >= 0; --k )
4608  {
4609  if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4610  {
4611  /* there should no variables fixed to one occur in our constraint */
4612  assert(SCIPvarGetLbLocal(vars[k]) < 0.5);
4613  assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4614 
4615  if( (*cliquevalues)[k] )
4616  {
4617  assert(SCIPvarIsActive(vars[k]));
4618  var = vars[k];
4619  }
4620  else
4621  {
4623  var = SCIPvarGetNegationVar(vars[k]);
4624  }
4625  if( !SCIPhaveVarsCommonClique(scip, var1, value, var, (*cliquevalues)[k], TRUE) )
4626  break;
4627  }
4628  }
4629  --v1;
4630  }
4631  /* variable index in the constraint is equal to the index of the other variable, check if these variables are
4632  * negated of each other so memorize the position and check for possible inclusion of the new variable and if
4633  * possible decrease indices
4634  */
4635  else
4636  {
4637  /* one clique contains the negated and the other clique the corresponding active var */
4638  if( value != (*cliquevalues)[v] )
4639  {
4640  nottocheck = v;
4641 
4642  assert(consdata == SCIPconsGetData(cons));
4643  assert(nvars <= consdata->nvars);
4644 
4645  /* check if every variable in the actual clique is in clique with the new variable */
4646  for( k = nvars - 1; k >= 0; --k )
4647  {
4648  if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4649  {
4650  /* there should no variables fixed to one occur in our constraint */
4651  assert(SCIPvarGetLbLocal(vars[k]) < 0.5);
4652 
4653  assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4654 
4655  if( k == nottocheck )
4656  continue;
4657 
4658  if( (*cliquevalues)[k] )
4659  {
4660  assert(SCIPvarIsActive(vars[k]));
4661  var = vars[k];
4662  }
4663  else
4664  {
4666  var = SCIPvarGetNegationVar(vars[k]);
4667  }
4668 
4669  if( !SCIPhaveVarsCommonClique(scip, var1, value, var, (*cliquevalues)[k], TRUE) )
4670  break;
4671  }
4672  }
4673  }
4674  /* don't decrease v because it might happen that the corresponding negated variable of var is next in
4675  * usefulvars
4676  */
4677  --v1;
4678  }
4679 
4680  /* if k is smaller than 0 than the possible new variables is in the same clique with all variables of cons,
4681  * so we add the new variable to clique constraint or fix some variables */
4682  if( k < 0 )
4683  {
4684  ++(*nadded);
4685 
4686  /* we found a variable which is the negated variable of another one in this clique so we can fix all
4687  * other variable to zero and if it's a partitioning constraint we can also fix the variable of the
4688  * negated to one and we can delete the constraint too */
4689  if( nottocheck >= 0 )
4690  {
4691  assert(consdata == SCIPconsGetData(cons));
4692  assert(nvars <= consdata->nvars);
4693  assert(consdata->merged);
4694 
4695  /* process all vars for possible fixing */
4696  for( k = consdata->nvars - 1; k >= 0; --k )
4697  {
4698  if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4699  {
4700  /* there should no variables fixed to one occur in our constraint */
4701  assert(SCIPvarGetLbLocal(vars[v]) < 0.5);
4702 
4703  assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4704 
4705  if( k != nottocheck )
4706  {
4707  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because we could lift a negated variable of another constraint variable\n", SCIPvarGetName(vars[k]));
4708  /* fix variable to zero */
4709  SCIP_CALL( SCIPfixVar(scip, vars[k], 0.0, cutoff, &fixed) );
4710 
4711  if( *cutoff )
4712  {
4713  SCIPdebugMsg(scip, "fixing led to cutoff\n");
4714 
4715  return SCIP_OKAY;
4716  }
4717 
4718  assert(fixed);
4719 
4720  ++(*nfixedvars);
4721  }
4722  }
4723  }
4724  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
4725  {
4726  assert(SCIPvarIsActive(vars[nottocheck]) || (SCIPvarGetStatus(vars[nottocheck]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[nottocheck]))));
4727 
4728  SCIPdebugMsg(scip, "trying to fix <%s> to 1 due to this setpartitioning variable is with its negated in the same clique\n", SCIPvarGetName(vars[nottocheck]));
4729  /* fix the remaining variable to one, due to it's the only one left to satisfy the constraint */
4730  SCIP_CALL( SCIPfixVar(scip, vars[nottocheck], 1.0, cutoff, &fixed) );
4731  if( *cutoff )
4732  {
4733  SCIPdebugMsg(scip, "fixing led to cutoff\n");
4734 
4735  return SCIP_OKAY;
4736  }
4737 
4738  assert(fixed);
4739  ++(*nfixedvars);
4740  }
4741 
4742  /* delete constraint */
4743  SCIPdebugMsg(scip, " -> deleting constraint <%s> number <%d> due to active and negated variable in the same clique constraint\n", SCIPconsGetName(cons), arraypos);
4744  assert(SCIPconsIsActive(cons));
4745  SCIP_CALL( SCIPdelCons(scip, cons) );
4746  ++(*ndelconss);
4747 
4748  break;
4749  }
4750  /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4751  else if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
4752  {
4753  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1 + 1]));
4754  /* fix variable to zero */
4755  SCIP_CALL( SCIPfixVar(scip, usefulvars[v1 + 1], 0.0, cutoff, &fixed) );
4756 
4757  if( *cutoff )
4758  {
4759  SCIPdebugMsg(scip, "fixing led to cutoff\n");
4760 
4761  return SCIP_OKAY;
4762  }
4763 
4764  assert(fixed);
4765 
4766  ++(*nfixedvars);
4767  }
4768  /* we have found a new variable for a set packing constraint cons, so add the found variable to the first constraint */
4769  else
4770  {
4771  SCIP_VAR* addvar;
4772 
4773  assert(SCIPconsIsActive(cons));
4774 
4775  addvar = usefulvars[v1 + 1];
4776 
4777  assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);
4778 
4779  /* add representative instead */
4780  SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(usefulvars[v1 + 1]), SCIPconsGetName(cons), arraypos);
4781  SCIP_CALL( addCoef(scip, cons, addvar) );
4782  assert(consdata == SCIPconsGetData(cons));
4783  /* we know that this constraint stays merged but later on we have to resort */
4784  consdata->merged = TRUE;
4785 
4786  /* second we add the constraint index to the list of indices where this variable occurs */
4787  assert(SCIPhashmapExists(vartoindex, (void*) addvar));
4788 
4789  /* correct local data structure, add constraint entry to variable data */
4790  SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4791 
4792  /* we need the new pointer to the variables, because due to adding variables it is possible that we
4793  * did reallocate the variables array inside the constraint, the index v should stay the same because the
4794  * added variable was inserted at the end and we are decreasing v in our for loop
4795  */
4796  vars = consdata->vars;
4797  nvars = consdata->nvars;
4798 
4799  /* we need to update our data structure */
4800 
4801  /* resize clique array if necessary, due to adding variables */
4802  if( (*maxnvars) < nvars )
4803  {
4804  while( (*maxnvars) < nvars )
4805  (*maxnvars) *= 2 ;
4806  SCIP_CALL( SCIPreallocBufferArray(scip, cliquevalues, (*maxnvars)) );
4807  }
4808  (*cliquevalues)[nvars - 1] = SCIPvarIsActive(addvar) ? TRUE : FALSE;
4809 
4810  (*chgcons) = TRUE;
4811  }
4812  }
4813  }
4814 
4815  if( !SCIPconsIsActive(cons) )
4816  return SCIP_OKAY;
4817 
4818  /* maybe we stopped because of cons(v reached -1) so try to add rest in usefulvars */
4819  for( ; v1 >= 0; --v1)
4820  {
4821  if( SCIPvarGetLbLocal(usefulvars[v1]) > 0.5 || SCIPvarGetUbLocal(usefulvars[v1]) < 0.5 )
4822  continue;
4823 
4824  /* get active variable and clique value */
4825  if( SCIPvarIsActive(usefulvars[v1]) )
4826  {
4827  var1 = usefulvars[v1];
4828  value = TRUE;
4829  }
4830  else
4831  {
4832  assert(SCIPvarGetStatus(usefulvars[v1]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(usefulvars[v1])));
4833  var1 = SCIPvarGetNegationVar(usefulvars[v1]);
4834  value = FALSE;
4835  }
4836 
4837  assert(consdata == SCIPconsGetData(cons));
4838  assert(nvars <= consdata->nvars);
4839 
4840  /* check if every variable in the actual clique is in clique with the new variable */
4841  for( k = nvars - 1; k >= 0; --k )
4842  {
4843  if( SCIPvarGetUbLocal(vars[k]) > 0.5 )
4844  {
4845  /* there should no variables fixed to one occur in our constraint */
4846  assert(SCIPvarGetLbLocal(vars[k]) < 0.5);
4847 
4848  assert(SCIPvarIsActive(vars[k]) || (SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_NEGATED && SCIPvarIsActive(SCIPvarGetNegationVar(vars[k]))));
4849 
4850  if( (*cliquevalues)[k] )
4851  {
4852  assert(SCIPvarIsActive(vars[k]));
4853  var = vars[k];
4854  }
4855  else
4856  {
4858  var = SCIPvarGetNegationVar(vars[k]);
4859  }
4860 
4861  if( !SCIPvarsHaveCommonClique(var1, value, var, (*cliquevalues)[k], TRUE) )
4862  break;
4863  }
4864  }
4865 
4866  /* add new variable to clique constraint or fix some variables */
4867  if( k < 0 )
4868  {
4869  /* we found a variable which could be added to a partitioning constraint so we can fix it to zero */
4870  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
4871  {
4872  SCIPdebugMsg(scip, "trying to fix <%s> to 0 because this variable is in the same clique with a set partition\n", SCIPvarGetName(usefulvars[v1]));
4873 
4874  /* fix variable to zero */
4875  SCIP_CALL( SCIPfixVar(scip, usefulvars[v1], 0.0, cutoff, &fixed) );
4876  if( *cutoff )
4877  {
4878  SCIPdebugMsg(scip, "fixing led to cutoff\n");
4879 
4880  return SCIP_OKAY;
4881  }
4882  assert(fixed);
4883 
4884  ++(*nfixedvars);
4885  ++(*nadded);
4886  }
4887  /* add the found variable to the first constraint */
4888  else
4889  {
4890  SCIP_VAR* addvar;
4891 
4892  assert(SCIPconsIsActive(cons));
4893 
4894  addvar = usefulvars[v1];
4895 
4896  assert(SCIPvarGetLbLocal(addvar) < 0.5 && SCIPvarGetUbLocal(addvar) > 0.5);
4897 
4898  /* add representative instead */
4899  SCIPdebugMsg(scip, " -> adding variable <%s> to constraint <%s> number %d\n", SCIPvarGetName(addvar), SCIPconsGetName(cons), arraypos);
4900  SCIP_CALL( addCoef(scip, cons, addvar) );
4901  assert(consdata == SCIPconsGetData(cons));
4902  /* we know that this constraint stays merged but later on we have to resort */
4903  consdata->merged = TRUE;
4904 
4905  /* second we add the constraint index to the list of indices where this variable occurs */
4906  assert(SCIPhashmapExists(vartoindex, (void*) addvar));
4907 
4908  /* correct local data structure, add constraint entry to variable data */
4909  SCIP_CALL( addCliqueDataEntry(scip, addvar, arraypos, FALSE, usefulvars, nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs) );
4910 
4911  /* we need the new pointer to the variables, because due to adding variables it is possible that we
4912  * did reallocate the variables array inside the constraint, the index v should stay the same because the
4913  * added variable was inserted at the end and we are decreasing v in our for loop
4914  */
4915  vars = consdata->vars;
4916  nvars = consdata->nvars;
4917 
4918  /* we need to update our data structure */
4919 
4920  /* resize clique array if necessary, due to adding variables */
4921  if( (*maxnvars) < nvars )
4922  {
4923  while( (*maxnvars) < nvars )
4924  (*maxnvars) *= 2 ;
4925  SCIP_CALL( SCIPreallocBufferArray(scip, cliquevalues, (*maxnvars)) );
4926  }
4927  (*cliquevalues)[nvars - 1] = SCIPvarIsActive(addvar) ? TRUE : FALSE;
4928 
4929  ++(*nadded);
4930  (*chgcons) = TRUE;
4931  }
4932  }
4933  }
4934 
4935  return SCIP_OKAY;
4936 }
4937 
4938 /** perform all collected aggregations */
4939 static
4941  SCIP*const scip, /**< SCIP data structure */
4942  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4943  SCIP_VAR**const undoneaggrvars, /**< aggregation variables storage */
4944  SCIP_Bool*const undoneaggrtypes, /**< aggregation type storage, type FALSE means the aggregation is of the
4945  * form x + y = 1; type TRUE means the aggregation is of the form x = y;
4946  */
4947  int const naggregations, /**< number of aggregations to performed */
4948  int*const naggrvars, /**< pointer to count number of aggregated variables */
4949  SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
4950  )
4951 { /*lint --e{715}*/
4952  SCIP_VAR* var1;
4953  SCIP_VAR* var2;
4954  SCIP_Bool aggregated;
4955  SCIP_Bool redundant;
4956  int a;
4957 
4958  assert(scip != NULL);
4959  assert(conshdlrdata != NULL);
4960  assert(undoneaggrvars != NULL);
4961  assert(undoneaggrtypes != NULL);
4962  assert(naggregations > 0);
4963  assert(naggrvars != NULL);
4964  assert(cutoff != NULL);
4965 
4966  /* loop over all open aggregations and try to aggregate them */
4967  for( a = 0; a < naggregations; ++a )
4968  {
4969  var1 = undoneaggrvars[2 * a];
4970  var2 = undoneaggrvars[2 * a + 1];
4971  assert(var1 != NULL);
4972  assert(var2 != NULL);
4973 
4974  SCIPdebugMsg(scip, "trying to aggregate <%s> %s <%s>%s\n", SCIPvarGetName(var1), undoneaggrtypes[a] ? "=" : "+", SCIPvarGetName(var2), undoneaggrtypes[a] ? "" : " = 1");
4975 
4976 #ifdef VARUSES
4977  /* in order to not mess up the variable usage counting, we have to decrease usage counting, aggregate,
4978  * and increase usage counting again
4979  */
4980  SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var1) );
4981  SCIP_CALL( conshdlrdataDecVaruses(scip, conshdlrdata, var2) );
4982 #endif
4983 
4984  /* aggregate last remaining variables in the set partitioning constraint */
4985  if( undoneaggrtypes[a] )
4986  {
4987  SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, -1.0, 0.0, cutoff, &redundant, &aggregated) );
4988  }
4989  else
4990  {
4991  SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, cutoff, &redundant, &aggregated) );
4992  }
4993 
4994  if( *cutoff )
4995  {
4996  SCIPdebugMsg(scip, "aggregation was infeasible\n");
4997 
4998  return SCIP_OKAY;
4999  }
5000  /* binary variables should always be aggregated, or due to fixation the aggregation is redundant */
5001  assert(redundant);
5002 
5003  if( aggregated )
5004  ++(*naggrvars);
5005 
5006 #ifdef VARUSES
5007  /* increase variable usage counting again */
5008  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var1) );
5009  SCIP_CALL( conshdlrdataIncVaruses(scip, conshdlrdata, var2) );
5010 #endif
5011  }
5012 
5013  return SCIP_OKAY;
5014 }
5015 
5016 /** check whether we can combine or grow cliques so some constraints become redundant or we can fix variables */
5017 /** @todo try another variant, by building up the clique graph and delete unnecessary (transitive closure) edges and do
5018  * a bfs search to search for common ancestors to get all possible lifting variables
5019  */
5020 static
5022  SCIP*const scip, /**< SCIP data structure */
5023  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
5024  SCIP_CONS**const conss, /**< constraint set */
5025  int const nconss, /**< number of constraints in constraint set */
5026  int const nrounds, /**< actual presolving round */
5027  int*const firstchange, /**< pointer to store first changed constraint */
5028  int*const firstclique, /**< pointer to store first constraint to start adding clique again */
5029  int*const lastclique, /**< pointer to store last constraint to add cliques again */
5030  int*const nfixedvars, /**< pointer to count number of deleted variables */
5031  int*const naggrvars, /**< pointer to count number of aggregated variables */
5032  int*const ndelconss, /**< pointer to count number of deleted constraints */
5033  int*const nchgcoefs, /**< pointer to count number of deleted coefficients */
5034  SCIP_Bool*const cutoff /**< pointer to store if the problem is infeasible due to a fixing */
5035  )
5036 {
5037  /* extend cliques/constraints by checking whether some variables are in the same clique, no pairwise clique lifting
5038  * which would be slower
5039  */
5040  SCIP_CONS** usefulconss; /* array with pointers of constraint of setpartitioning and setpacking type */
5041  SCIP_VAR** usefulvars; /* array with pointers of variables in setpartitioning and setpacking constraints */
5042  int** varconsidxs; /* array consisting of constraint indices in which the corresponding variable exists */
5043  int* varnconss; /* array consisting of number of constraints the variable occurs */
5044  int* maxnvarconsidx; /* maximal number of occurrences of a variable */
5045  int* countofoverlapping = NULL; /* the amount of variables which are in another constraint */
5046  SCIP_Bool* cliquevalues = NULL; /* values of clique-variables, either one if the variable is active or zero if the variable is negated */
5047 
5048  SCIP_HASHMAP* vartoindex; /* mapping of SCIP variables to indices */
5049  SCIP_CONSDATA* consdata;
5050 
5051  SCIP_Bool chgcons0;
5052  int nvars;
5053  int c;
5054  int v;
5055  int nusefulconss;
5056  int nusefulvars;
5057  int susefulvars;
5058  int maxnvars;
5059  int varindex;
5060 
5061  SCIP_VAR** undoneaggrvars; /* storage for not yet performed aggregations */
5062  SCIP_Bool* undoneaggrtypes; /* storage for not yet performed aggregation type (x = y or x + y = 1) */
5063  int saggregations;
5064  int naggregations;
5065 
5066  assert(scip != NULL);
5067  assert(conshdlrdata != NULL);
5068  assert(conss != NULL || nconss == 0);
5069  assert(firstchange != NULL);
5070  assert(firstclique != NULL);
5071  assert(lastclique != NULL);
5072  assert(nfixedvars != NULL);
5073  assert(naggrvars != NULL);
5074  assert(ndelconss != NULL);
5075  assert(nchgcoefs != NULL);
5076  assert(cutoff != NULL);
5077 
5078  *cutoff = FALSE;
5079 
5080  if( nconss == 0 )
5081  return SCIP_OKAY;
5082 
5083  nvars = SCIPgetNVars(scip);
5084 
5085  if( nvars == 0 )
5086  return SCIP_OKAY;
5087 
5088  susefulvars = 2 * nvars; /* two times because of negated vars, maybe due to deleted variables we need to increase this */
5089 
5090  /* a hashmap from varindex to postion in varconsidxs array, because above is still too small */
5091  SCIP_CALL( SCIPhashmapCreate(&vartoindex, SCIPblkmem(scip), nvars) );
5092 
5093  /* get temporary memory for the aggregation storage, to memorize aggregations which will be performed later, otherwise we would destroy our local data structures */
5094  saggregations = nvars;
5095  SCIP_CALL( SCIPallocBufferArray(scip, &undoneaggrvars, 2 * saggregations) );
5096  SCIP_CALL( SCIPallocBufferArray(scip, &undoneaggrtypes, saggregations) );
5097  BMSclearMemoryArray(undoneaggrtypes, saggregations);
5098  naggregations = 0;
5099 
5100  /* get temporary memory for all clique constraints, all appearing variables and the mapping from variables to constraints */
5101  SCIP_CALL( SCIPallocBufferArray(scip, &usefulconss, nconss) );
5102  SCIP_CALL( SCIPallocBufferArray(scip, &usefulvars, susefulvars) );
5103  BMSclearMemoryArray(usefulvars, susefulvars);
5104  SCIP_CALL( SCIPallocBufferArray(scip, &varnconss, susefulvars + 1) );
5105  BMSclearMemoryArray(varnconss, susefulvars + 1);
5106  SCIP_CALL( SCIPallocBufferArray(scip, &maxnvarconsidx, susefulvars + 1) );
5107  SCIP_CALL( SCIPallocBufferArray(scip, &varconsidxs, susefulvars + 1) );
5108  BMSclearMemoryArray(varconsidxs, susefulvars + 1);
5109  nusefulvars = 0;
5110  nusefulconss = 0;
5111  maxnvars = 0;
5112 
5113  /* @todo: check for round limit for adding extra clique constraints */
5114  /* adding clique constraints which arises from global clique information */
5115  if( conshdlrdata->nclqpresolve == 0 && conshdlrdata->addvariablesascliques )
5116  {
5117  SCIP_VAR** vars = SCIPgetVars(scip);
5118  SCIP_VAR** binvars;
5119  int* cliquepartition;
5120  int ncliques;
5121  int nbinvars;
5122  int naddconss;
5123 
5124  nbinvars = SCIPgetNBinVars(scip);
5125  SCIP_CALL( SCIPduplicateBufferArray(scip, &binvars, vars, nbinvars) );
5126  SCIP_CALL( SCIPallocBufferArray(scip, &cliquepartition, nbinvars) );
5127 
5128  /* @todo: check for better permutations/don't permute the first round
5129  * @todo: take binary variables which are not of vartype SCIP_VARTYPE_BINARY into account
5130  */
5131  SCIPrandomPermuteArray(conshdlrdata->randnumgen, (void**)binvars, 0, nbinvars);
5132 
5133  /* try to create a clique-partition over all binary variables and create these cliques as new setppc constraints
5134  * and add them to the usefulconss array and adjust all necessary data this will hopefully lead to faster
5135  * detection of redundant constraints
5136  */
5137  SCIP_CALL( SCIPcalcCliquePartition(scip, binvars, nbinvars, cliquepartition, &ncliques) );
5138 
5139  /* resize usefulconss array if necessary */
5140  SCIP_CALL( SCIPreallocBufferArray(scip, &usefulconss, nconss + ncliques) );
5141 
5142  naddconss = 0;
5143 
5144  /* add extra clique constraints resulting from the cliquepartition calculation to SCIP and to the local data structure */
5145  SCIP_CALL( addExtraCliques(scip, binvars, nbinvars, cliquepartition, ncliques, usefulconss, &nusefulconss,
5146  nrounds, nfixedvars, &naddconss, ndelconss, nchgcoefs, cutoff) );
5147 
5148  /* bad hack, we don't want to count these artificial created constraints if they got deleted, so ndelconss
5149  * can become negative which will be change to zero at the end of this method if it's still negative
5150  */
5151  *ndelconss -= naddconss;
5152 
5153  SCIPfreeBufferArray(scip, &cliquepartition);
5154  SCIPfreeBufferArray(scip, &binvars);
5155 
5156  if( *cutoff )
5157  goto TERMINATE;
5158  }
5159 
5160  /* start to collect setpartitioning and setpacking constraints, and try to remove fixed variables and merged these
5161  * constraints
5162  */
5163  SCIP_CALL( collectCliqueConss(scip, conss, nconss, usefulconss, &nusefulconss, nfixedvars, ndelconss, nchgcoefs, cutoff) );
5164  /* @Note: Even after the call above some constraints can have fixed variables, because it might happen that caused by
5165  * mergeMultiplies some variables were fixed which occurred already in previous constraints
5166  */
5167  if( *cutoff )
5168  goto TERMINATE;
5169 
5170  /* no usefulconss found */
5171  if( nusefulconss <= 1 )
5172  goto TERMINATE;
5173 
5174  /* @todo: maybe sort them after biggest indices too, or another variant would be to restore the order as they were
5175  * read in
5176  */
5177  /* sort constraints first after type (partitioning before packing) and second after number of variables such that the
5178  * partitioning constraints have increasing number of variables and the packing constraints have decreasing number of
5179  * variables, because we loop from back to front we sort them downwards, so they are the other way around
5180  */
5181  SCIPsortDownPtr((void**)usefulconss, setppcConssSort, nusefulconss);
5182 
5183  /* creating all necessary data in array structure, collect all clique constraint variables and occurrences */
5184  SCIP_CALL( collectCliqueData(scip, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs, &maxnvars) );
5185  assert(maxnvars > 0);
5186 
5187  /* allocate temporary memory for actual clique */
5188  SCIP_CALL( SCIPallocBufferArray(scip, &cliquevalues, maxnvars) );
5189  /* allocate temporary memory for counting an overlap of variables */
5190  SCIP_CALL( SCIPallocBufferArray(scip, &countofoverlapping, nusefulconss) );
5191 
5192  /* sort usefulvars after indices of variables, negated and active counterparts will stand side by side */
5193  SCIPsortDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, nusefulvars);
5194 
5195  /* extend cliques/constraints by checking whether some variables of a second constraint are in the same clique */
5196  for( c = nusefulconss - 1; c >= 0 && !SCIPisStopped(scip); --c )
5197  {
5198  SCIP_VAR** cons0vars; /* these are the clique variables */
5199  SCIP_CONS* cons0;
5200  int ncons0vars;
5201  SCIP_VAR* var0;
5202  int v1;
5203  int nadded; /* number of possible added variables to constraint */
5204  int cons0fixedzeros;
5205  int oldnchgcoefs;
5206 #ifndef NDEBUG
5207  const int oldnaggrvars = *naggrvars;
5208 #endif
5209  cons0 = usefulconss[c];
5210 
5211  if( !SCIPconsIsActive(cons0) )
5212  continue;
5213 
5214  /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5215  * possible
5216  */
5217  SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5218 
5219  if( *cutoff )
5220  break;
5221 
5222  /* we can't handle aggregated variables later on so we should have saved them for later */
5223  assert(*naggrvars == oldnaggrvars);
5224 
5225  if( !SCIPconsIsActive(cons0) )
5226  continue;
5227 
5228  /* we need to determine the cliquedata in each iteration because we eventual will change it later */
5229  consdata = SCIPconsGetData(cons0);
5230  assert(consdata != NULL);
5231 
5232  cons0vars = consdata->vars;
5233  ncons0vars = consdata->nvars;
5234 
5235  /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5236  SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
5237  /* standard setppc-sorting now lost */
5238  consdata->sorted = FALSE;
5239 
5240  /* clique array should be long enough */
5241  assert(maxnvars >= ncons0vars);
5242 
5243  /* clear old entries in overlapping constraint */
5244  BMSclearMemoryArray(countofoverlapping, nusefulconss);
5245 
5246  /* calculate overlapping */
5247  for( v = ncons0vars - 1; v >= 0 ; --v )
5248  {
5249  var0 = cons0vars[v];
5250 
5251  /* fixed variables later to the count */
5252  if( SCIPvarGetLbLocal(var0) > 0.5 || SCIPvarGetUbLocal(var0) < 0.5 )
5253  continue;
5254 
5255  assert(SCIPhashmapExists(vartoindex, (void*) var0));
5256 
5257  varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var0);
5258  for( v1 = varnconss[varindex] - 1; v1 >= 0 ; --v1 )
5259  ++(countofoverlapping[varconsidxs[varindex][v1]]);
5260  }
5261 
5262  oldnchgcoefs = *nchgcoefs;
5263  cons0fixedzeros = consdata->nfixedzeros;
5264 
5265  chgcons0 = FALSE;
5266 
5267  /* check for overlapping constraint before starting lifting */
5268  SCIP_CALL( checkForOverlapping(scip, cons0, c, c, usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex,
5269  varnconss, maxnvarconsidx, varconsidxs, countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
5270  undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations,
5271  nfixedvars, naggrvars, nchgcoefs, ndelconss, cutoff) );
5272 
5273  if( *cutoff )
5274  break;
5275 
5276  /* we can't handle aggregated variables later on so we should have saved them for later */
5277  assert(*naggrvars == oldnaggrvars);
5278 
5279  /* if cons0 changed, we need to reorder the variables */
5280  if( chgcons0 && *nchgcoefs > oldnchgcoefs )
5281  {
5282  consdata = SCIPconsGetData(cons0);
5283  assert(consdata != NULL);
5284 
5285  cons0vars = consdata->vars;
5286  ncons0vars = consdata->nvars;
5287 
5288  /* sorting array after indices of variables, negated and active counterparts will stand side by side */
5289  SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
5290  /* standard setppc-sorting now lost */
5291  consdata->sorted = FALSE;
5292  }
5293 
5294  /* check cons0 again for redundancy/fixings, because due to fixings in all other constraints it might happen that cons0 is redundant now */
5295  if( consdata->nfixedones > 0 || consdata->nfixedzeros > cons0fixedzeros )
5296  {
5297  /* check if constraint is already redundant or infeasible due to fixings, fix or aggregate left over variables if
5298  * possible
5299  */
5300  SCIP_CALL( presolvePropagateCons(scip, cons0, FALSE, undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations, nfixedvars, naggrvars, ndelconss, cutoff) );
5301 
5302  if( *cutoff )
5303  break;
5304 
5305  /* we can't handle aggregated variables later on so we should have saved them for later */
5306  assert(*naggrvars == oldnaggrvars);
5307 
5308  if( !SCIPconsIsActive(cons0) )
5309  continue;
5310  }
5311 
5312  nadded = 0;
5313 
5314  /* iterate over the cliques variables and all possible new clique variables at the "same" time, determine starting
5315  * index
5316  *
5317  * @note: it might be better to start the first round with our computed v1, but maybe it's better to switch to
5318  * trying to add all variables the second time for set packing constraints
5319  */
5320 
5321  /* we try to add all variables to the partitioning constraints, to try to fix as much as possible */
5322  if( consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING ) /*lint !e641*/
5323  v1 = nusefulvars - 1;
5324  else
5325  {
5326  /* if we already ran a presolving round we want to try to add new variables */
5327  if( conshdlrdata->nclqpresolve > 0 )
5328  v1 = nusefulvars - 1;
5329  else
5330  {
5331  /* find start position of variable which we will try to add to our constraint, so we will get better clique constraints */
5332  (void) SCIPsortedvecFindDownPtr((void**)usefulvars, SCIPvarCompActiveAndNegated, (void*)cons0vars[ncons0vars - 1], nusefulvars, &v1);
5333  assert(v1 >= 0 && v1 < nusefulvars);
5334  /* if constraint is not merged and we found a variable which is negated the same as it's neighbour we have to
5335  * increase v1 to make sure that we don't loose this important variable */
5336  if( v1 + 1 < nusefulvars && ((SCIPvarIsNegated(usefulvars[v1 + 1]) && SCIPvarGetNegatedVar(usefulvars[v1 + 1]) == usefulvars[v1]) || (SCIPvarIsNegated(usefulvars[v1]) && SCIPvarGetNegatedVar(usefulvars[v1]) == usefulvars[v1 + 1])) )
5337  ++v1;
5338  }
5339  }
5340 
5341  assert(maxnvars >= ncons0vars);
5342  /* initialize the cliquevalues array */
5343  for( v = ncons0vars - 1; v >= 0; --v )
5344  {
5345  if( SCIPvarGetLbLocal(cons0vars[v]) < 0.5 && SCIPvarGetUbLocal(cons0vars[v]) > 0.5 )
5346  {
5347  /* variable has to be either active or a negated variable of an active one */
5348  assert(SCIPvarIsActive(cons0vars[v]) || (SCIPvarGetStatus(cons0vars[v]) == SCIP_VARSTATUS_NEGATED &&
5349  SCIPvarIsActive(SCIPvarGetNegationVar(cons0vars[v]))));
5350  cliquevalues[v] = SCIPvarIsActive(cons0vars[v]) ? TRUE : FALSE;
5351  }
5352  }
5353 
5354  chgcons0 = FALSE;
5355 
5356  /* try to lift variables to cons0 */
5357  SCIP_CALL( liftCliqueVariables(scip, cons0, c, usefulvars, &nusefulvars, v1, &cliquevalues, vartoindex, varnconss,
5358  maxnvarconsidx, varconsidxs, &maxnvars, &nadded, &chgcons0, nfixedvars, ndelconss, cutoff) );
5359 
5360  if( *cutoff )
5361  break;
5362 
5363  if( !SCIPconsIsActive(cons0) )
5364  continue;
5365 
5366  /* check for redundant constraints due to changing cons0 */
5367  if( chgcons0 )
5368  {
5369  int i;
5370 
5371  *firstchange = MIN(*firstchange, c);
5372  *firstclique = MIN(*firstclique, c);
5373  *lastclique = MAX(*lastclique, c);
5374 
5375  /* variables array has changed due to lifting variables, so get new values */
5376  assert(consdata == SCIPconsGetData(cons0));
5377  cons0vars = consdata->vars;
5378  ncons0vars = consdata->nvars;
5379 
5380  /* resorting array, because we added new variables, in order of indices of variables, negated
5381  * and active counterparts would stand side by side
5382  */
5383  SCIPsortDownPtr((void**)cons0vars, SCIPvarCompActiveAndNegated, ncons0vars);
5384  /* standard setppc-sorting now lost */
5385  consdata->sorted = FALSE;
5386 
5387  /* clear old entries in overlapping constraint */
5388  BMSclearMemoryArray(countofoverlapping, nusefulconss);
5389 
5390  for( v = ncons0vars - 1; v >= 0 ; --v )
5391  {
5392  var0 = cons0vars[v];
5393 
5394  /* fixed variables later to the count */
5395  if( SCIPvarGetLbLocal(var0) > 0.5 || SCIPvarGetUbLocal(var0) < 0.5 )
5396  continue;
5397 
5398  assert(SCIPhashmapExists(vartoindex, (void*) var0));
5399 
5400  varindex = SCIPhashmapGetImageInt(vartoindex, (void*) var0);
5401  for( i = varnconss[varindex] - 1; i >= 0 ; --i )
5402  ++(countofoverlapping[varconsidxs[varindex][i]]);
5403  }
5404 
5405  chgcons0 = FALSE;
5406 
5407  /* check for overlapping constraint after lifting, in the first round we will only check up front */
5408  SCIP_CALL( checkForOverlapping(scip, cons0, c, (conshdlrdata->nclqpresolve > 0) ? nusefulconss : c,
5409  usefulconss, nusefulconss, usefulvars, &nusefulvars, vartoindex, varnconss, maxnvarconsidx, varconsidxs,
5410  countofoverlapping, conshdlrdata->cliqueshrinking, &chgcons0,
5411  undoneaggrvars, undoneaggrtypes, &naggregations, &saggregations,
5412  nfixedvars, naggrvars, nchgcoefs, ndelconss, cutoff) );
5413 
5414  if( *cutoff )
5415  break;
5416 
5417  /* we can't handle aggregated variables later on so we should have saved them for later */
5418  assert(*naggrvars == oldnaggrvars);
5419  }
5420  }
5421 
5422  TERMINATE:
5423  SCIPfreeBufferArrayNull(scip, &countofoverlapping);
5424  SCIPfreeBufferArrayNull(scip, &cliquevalues);
5425 
5426  /* free temporary memory for constraints, variables and the mapping between them in reverse order as they were
5427  * allocated
5428  */
5429  for( c = nusefulvars; c > 0; --c )
5430  {
5431  if( varconsidxs[c] != NULL )
5432  {
5433  SCIPfreeBufferArrayNull(scip, &(varconsidxs[c]));
5434  }
5435  }
5436 
5437  SCIPfreeBufferArray(scip, &varconsidxs);
5438  SCIPfreeBufferArray(scip, &maxnvarconsidx);
5439  SCIPfreeBufferArray(scip, &varnconss);
5440  SCIPfreeBufferArray(scip, &usefulvars);
5441  SCIPfreeBufferArray(scip, &usefulconss);
5442 
5443  /* perform all collected aggregations */
5444  if( !*cutoff && naggregations > 0 && !SCIPdoNotAggr(scip) )
5445  {
5446  SCIP_CALL( performAggregations(scip, conshdlrdata, undoneaggrvars, undoneaggrtypes, naggregations, naggrvars, cutoff) );
5447  }
5448 
5449  /* free temporary memory for the aggregation storage */
5450  SCIPfreeBufferArray(scip, &undoneaggrtypes);
5451  SCIPfreeBufferArray(scip, &undoneaggrvars);
5452 
5453  /* free hashmap */
5454  SCIPhashmapFree(&vartoindex);
5455 
5456  if( *ndelconss < 0 )
5457  *ndelconss = 0;
5458 
5459  return SCIP_OKAY;
5460 }
5461 
5462 
5463 /** add cliques to SCIP */
5464 static
5466  SCIP* scip, /**< SCIP data structure */
5467  SCIP_CONS** conss, /**< constraint set */
5468  int nconss, /**< number of constraints in constraint set */
5469  int firstclique, /**< first constraint to start to add cliques */
5470  int lastclique, /**< last constraint to start to add cliques */
5471  int* naddconss, /**< pointer to count number of added constraints */
5472  int* ndelconss, /**< pointer to count number of deleted constraints */
5473  int* nchgbds, /**< pointer to count number of changed bounds */
5474  SCIP_Bool* cutoff /**< pointer to store if the problem is infeasible due to a fixing */
5475  )
5476 {
5477  SCIP_CONS* cons;
5478  SCIP_CONSDATA* consdata;
5479  SCIP_Bool infeasible;
5480  int nlocalbdchgs;
5481  int c;
5482 
5483  assert(scip != NULL);
5484  assert(firstclique >= 0);
5485  assert(lastclique <= nconss);
5486  assert(conss != NULL || ((nconss == 0) && (lastclique == 0)));
5487 
5488  /* add clique and implication information */
5489  for( c = firstclique; c < lastclique; ++c )
5490  {
5491  cons = conss[c]; /*lint !e613*/
5492  assert(cons != NULL);
5493 
5494  /* ignore deleted constraints */
5495  if( !SCIPconsIsActive(cons) )
5496  continue;
5497 
5498  nlocalbdchgs = 0;
5499  SCIP_CALL( applyFixings(scip, cons, naddconss, ndelconss, &nlocalbdchgs, cutoff) );
5500  *nchgbds += nlocalbdchgs;
5501 
5502  if( *cutoff )
5503  return SCIP_OKAY;
5504 
5505  consdata = SCIPconsGetData(cons);
5506  assert(consdata != NULL);
5507 
5508  if( SCIPconsIsDeleted(cons) )
5509  continue;
5510 
5511  if( !consdata->cliqueadded && consdata->nvars >= 2 )
5512  {
5513  /* add a set partitioning / packing constraint as clique */
5514  if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING || (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
5515  {
5516  SCIP_CALL( SCIPaddClique(scip, consdata->vars, NULL, consdata->nvars,
5517  ((SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PARTITIONING), &infeasible, &nlocalbdchgs) );
5518  *nchgbds += nlocalbdchgs;
5519 
5520  if( infeasible )
5521  {
5522  *cutoff = TRUE;
5523  return SCIP_OKAY;
5524  }
5525  }
5526  else if( consdata->nvars == 2 && !SCIPconsIsModifiable(cons) )
5527  {
5528  /* a two-variable set covering constraint x + y >= 1 yields the implication x == 0 -> y == 1 */
5529  SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], FALSE, consdata->vars[1],
5530  SCIP_BOUNDTYPE_LOWER, 1.0, &infeasible, &nlocalbdchgs) );
5531  *nchgbds += nlocalbdchgs;
5532 
5533  if( infeasible )
5534  {
5535  *cutoff = TRUE;
5536  return SCIP_OKAY;
5537  }
5538  }
5539  consdata->cliqueadded = TRUE;
5540  }
5541  }
5542 
5543  return SCIP_OKAY;
5544 }
5545 
5546 /** perform multi-aggregation on variables resulting from a set-partitioning/-packing constraint */
5547 static
5549  SCIP* scip, /**< SCIP data structure */
5550  SCIP_Bool linearconshdlrexist,/**< does the linear constraint handler exist, necessary for multi-aggregations */
5551  SCIP_VAR** vars, /**< all variables including the variable to which will be multi-aggregated */
5552  int nvars, /**< number of all variables */
5553  int pos, /**< position of variable for multi-aggregation */
5554  SCIP_Bool* infeasible, /**< pointer to store infeasibility status of aggregation */
5555  SCIP_Bool* aggregated /**< pointer to store aggregation status */
5556  )
5557 {
5558  SCIP_VAR** tmpvars;
5559  SCIP_Real* scalars;
5560  int v;
5561 
5562  assert(scip != NULL);
5563  assert(vars != NULL);
5564  assert(nvars > 1);
5565  assert(0 <= pos && pos < nvars);
5566  assert(infeasible != NULL);
5567  assert(aggregated != NULL);
5568 
5569  if( nvars == 2 )
5570  {
5571  SCIP_Bool redundant;
5572 
5573  /* perform aggregation on variables resulting from a set-packing constraint */
5574  SCIP_CALL( SCIPaggregateVars(scip, vars[pos], vars[nvars - pos - 1], 1.0, 1.0, 1.0, infeasible, &redundant, aggregated) );
5575 
5576  if( *aggregated )
5577  SCIPdebugMsg(scip, "aggregated %s = 1 - %s\n", SCIPvarGetName(vars[pos]), SCIPvarGetName(vars[nvars - pos - 1]));
5578 
5579  return SCIP_OKAY;
5580  }
5581 
5582  if( !linearconshdlrexist )
5583  {
5584  *infeasible = FALSE;
5585  return SCIP_OKAY;
5586  }
5587 
5588  /* if the last variable will be multi-aggregated, we do not need to copy the variables */
5589  if( pos == nvars - 1 )
5590  tmpvars = vars;
5591  else
5592  {
5593  /* copy variables for aggregation */
5594  SCIP_CALL( SCIPduplicateBufferArray(scip, &tmpvars, vars, nvars) );
5595  tmpvars[pos] = tmpvars[nvars - 1];
5596  }
5597 
5598  SCIP_CALL( SCIPallocBufferArray(scip, &scalars, nvars - 1) );
5599  /* initialize scalars */
5600  for( v = nvars - 2; v >= 0; --v )
5601  scalars[v] = -1.0;
5602 
5603  SCIPdebugMsg(scip, "multi-aggregating binary variable <%s> (locks: [%d,%d]; to %d variables)\n",
5605  SCIPvarGetNLocksUpType(vars[pos], SCIP_LOCKTYPE_MODEL), nvars - 1);
5606 
5607  /* perform multi-aggregation */
5608  SCIP_CALL( SCIPmultiaggregateVar(scip, vars[pos], nvars - 1, tmpvars, scalars, 1.0, infeasible, aggregated) );
5609  assert(!(*infeasible));
5610 
5611  SCIPfreeBufferArray(scip, &scalars);
5612 
5613  if( pos < nvars - 1 )
5614  {
5615  assert(tmpvars != vars);
5616  SCIPfreeBufferArray(scip, &tmpvars);
5617  }
5618 
5619  return SCIP_OKAY;
5620 }
5621 
5622 /** determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and negated)
5623  * in any combination of set-partitioning and set-packing constraints
5624  *
5625  * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint or
5626  * even delete it
5627  *
5628  * 1. c1: x + y + z = 1, uplocks(x) = 1, downlocks(x) = 1 => x = 1 - y - z and change c1 to y + z <= 1
5629  *
5630  * 2. c2: x + y + z <= 1, uplocks(x) = 1, downlocks(x) = 0, obj(x) < 0 => x = 1 - y - z and change c2 to y + z <= 1
5631  *
5632  * 3. d1: x + y + z <= 1 and d2: ~x + u + v <= 1, uplocks(x) = 1, downlocks(x) = 1
5633  * a) obj(x) <= 0 => x = 1 - y - z and delete d1
5634  * b) obj(x) > 0 => ~x = 1 - u - v and delete d2
5635  *
5636  * 4. e1: x + y + z == 1 and e2: ~x + u + v (<= or ==) 1, uplocks(x) = (1 or 2), downlocks(x) = 2
5637  * => x = 1 - y - z and delete e1
5638  *
5639  * we can also aggregate a variable in a set-packing constraint with only two variables when the uplocks are equal to
5640  * one and then delete this constraint
5641  *
5642  * 5. f1: x + y <= 1, uplocks(x) = 1, obj(x) <= 0 => x = 1 - y and delete f1
5643  *
5644  * @todo might want to multi-aggregate variables even with more locks, when the fill in is still smaller or equal to
5645  * the old number of non-zeros, e.g.
5646  *
5647  * x + y + z = 1
5648  * ~x + u + v <=/= 1
5649  * ~x + w <= 1
5650  */
5651 static
5653  SCIP* scip, /**< SCIP data structure */
5654  SCIP_CONS** conss, /**< constraint set */
5655  int nconss, /**< number of constraints in constraint set */
5656  SCIP_Bool dualpresolvingenabled,/**< is dual presolving enabled */
5657  SCIP_Bool linearconshdlrexist,/**< does the linear constraint handler exist, necessary for
5658  * multi-aggregations
5659  */
5660  int* nfixedvars, /**< pointer to count number of deleted variables */
5661  int* naggrvars, /**< pointer to count number of aggregated variables */
5662  int* ndelconss, /**< pointer to count number of deleted constraints */
5663  int* nchgcoefs, /**< pointer to count number of changed coefficients */
5664  int* nchgsides, /**< pointer to count number of changed left hand sides */
5665  SCIP_Bool* cutoff /**< pointer to store if a cut off was detected */
5666  )
5667 {
5668  SCIP_CONS** usefulconss;
5669  SCIP_VAR** binvars;
5670  SCIP_HASHMAP* vartoindex;
5671  SCIP_Bool* chgtype;
5672  int* considxs;
5673  int* posincons;
5674  SCIP_Bool infeasible;
5675  SCIP_Bool aggregated;
5676  SCIP_Bool donotaggr;
5677  SCIP_Bool donotmultaggr;
5678  SCIP_Bool mustcheck;
5679  SCIP_Bool addcut;
5680  int nposvars;
5681  int ndecs;
5682  int nbinvars;
5683  int nposbinvars;
5684  int nuplocks;
5685  int ndownlocks;
5686 #ifndef NDEBUG
5687  int posreplacements = 0;
5688 #endif
5689  int nhashmapentries;
5690  int nlocaladdconss;
5691  int v;
5692  int c;
5693 
5694  assert(scip != NULL);
5695  assert(conss != NULL);
5696  assert(nconss > 0);
5697  assert(nfixedvars != NULL);
5698  assert(naggrvars != NULL);
5699  assert(ndelconss != NULL);
5700  assert(nchgcoefs != NULL);
5701  assert(nchgsides != NULL);
5702 
5703  nbinvars = SCIPgetNBinVars(scip);
5704  nposbinvars = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
5705  assert(nbinvars + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip) == nposbinvars);
5706 
5707  binvars = SCIPgetVars(scip);
5708 
5709  /* determine number for possible multi-aggregations */
5710  nposvars = 0;
5711  for( v = nposbinvars - 1; v >= 0; --v )
5712  {
5713  assert(SCIPvarGetType(binvars[v]) != SCIP_VARTYPE_CONTINUOUS);
5714 
5715  if( v < nbinvars || SCIPvarIsBinary(binvars[v]) )
5716  {
5717  nuplocks = SCIPvarGetNLocksUpType(binvars[v], SCIP_LOCKTYPE_MODEL);
5718  ndownlocks = SCIPvarGetNLocksDownType(binvars[v], SCIP_LOCKTYPE_MODEL);
5719 
5720  if( (nuplocks == 1 && ndownlocks <= 1) || (nuplocks <= 1 && ndownlocks == 1) || (nuplocks <= 2 && ndownlocks <= 2 && SCIPvarGetNegatedVar(binvars[v]) != NULL) )
5721  ++nposvars;
5722  }
5723  }
5724 
5725  SCIPdebugMsg(scip, "found %d binary variables for possible multi-aggregation\n", nposvars);
5726 
5727  if( nposvars == 0 )
5728  return SCIP_OKAY;
5729 
5730  /* a hashmap from var to index when found in a set-partitioning constraint */
5731  SCIP_CALL( SCIPhashmapCreate(&vartoindex, SCIPblkmem(scip), nposvars) );
5732 
5733  /* get temporary memory */
5734  SCIP_CALL( SCIPallocBufferArray(scip, &chgtype, nconss) );
5735  BMSclearMemoryArray(chgtype, nconss);
5736 
5737  SCIP_CALL( SCIPallocBufferArray(scip, &considxs, nposbinvars) );
5738  SCIP_CALL( SCIPallocBufferArray(scip, &posincons, nposbinvars) );
5739 
5740  SCIP_CALL( SCIPduplicateBufferArray(scip, &usefulconss, conss, nconss) );
5741  /* sort constraints */
5742  SCIPsortPtr((void**)usefulconss, setppcConssSort2, nconss);
5743 
5744  nhashmapentries = 0;
5745  ndecs = 0;
5746  donotaggr = SCIPdoNotAggr(scip);
5747  donotmultaggr = SCIPdoNotMultaggr(scip);
5748  assert(!donotaggr || !donotmultaggr);
5749 
5750  /* determine singleton variables in set-partitioning/-packing constraints, or doubleton variables (active and
5751  * negated) in any combination of set-partitioning and set-packing constraints
5752  *
5753  * we can multi-aggregate the variable and either change the set-partitioning constraint to a set-packing constraint
5754  * or even delete it
5755  */
5756  for( c = 0; c < nconss; ++c )
5757  {
5758  SCIP_CONS* cons;
5759  SCIP_CONSDATA* consdata;
5760  int oldnfixedvars;
5761  nlocaladdconss = 0;
5762 
5763  cons = usefulconss[c];
5764  assert(cons != NULL);
5765 
5766  if( SCIPconsIsDeleted(cons) )
5767  continue;
5768 
5769  consdata = SCIPconsGetData(cons);
5770  assert(consdata != NULL);
5771 
5772  /* if we cannot find any constraint to perform a useful multi-aggregation, stop */
5773  if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_COVERING )
5774  break;
5775 
5776  if( !SCIPconsIsChecked(cons) )
5777  continue;
5778 
5779  if( SCIPconsIsModifiable(cons) )
5780  continue;
5781 
5782  /* update the variables */
5783  SCIP_CALL( applyFixings(scip, cons, &nlocaladdconss, ndelconss, nfixedvars, cutoff) );
5784 
5785  if( *cutoff )
5786  break;
5787 
5788  /* due to resolving multi-aggregations a constraint can become deleted */
5789  if( SCIPconsIsDeleted(cons) )
5790  continue;
5791 
5792  SCIP_CALL( processFixings(scip, cons, cutoff, nfixedvars, &addcut, &mustcheck) );
5793  assert(!addcut);
5794 
5795  if( *cutoff )
5796  break;
5797 
5798  if( SCIPconsIsDeleted(cons) )
5799  continue;
5800 
5801  oldnfixedvars = *nfixedvars;
5802 
5803  /* merging unmerged constraints */
5804  SCIP_CALL( mergeMultiples(scip, cons, nfixedvars, ndelconss, nchgcoefs, cutoff) );
5805 
5806  if( *cutoff )
5807  break;
5808 
5809  if( SCIPconsIsDeleted(cons) )
5810  continue;
5811 
5812  if( oldnfixedvars < *nfixedvars )
5813  {
5814  /* update the variables */
5815  SCIP_CALL( applyFixings(scip, cons, &nlocaladdconss, ndelconss, nfixedvars, cutoff) );
5816  assert(!SCIPconsIsDeleted(cons));
5817  assert(nlocaladdconss == 0);
5818  assert(!*cutoff);
5819 
5820  if( SCIPconsIsDeleted(cons) )
5821  continue;
5822  }
5823 
5824  /* if the constraint was not merged and consists of a variable with its negation, the constraint is redundant */
5825  if( consdata->nvars < 2 )
5826  {
5827  /* deleting redundant set-packing constraint */
5828  if( (SCIP_SETPPCTYPE)consdata->setppctype == SCIP_SETPPCTYPE_PACKING )
5829  {
5830  SCIPdebugMsg(scip, "deleting redundant set-packing constraint <%s>\n", SCIPconsGetName(cons));
5831 
5832  SCIP_CALL( SCIPdelCons(scip, cons) );
5833  ++(*nd