Scippy

SCIP

Solving Constraint Integer Programs

cons_cardinality.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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_cardinality.c
17  * @brief constraint handler for cardinality constraints
18  * @author Tobias Fischer
19  *
20  * This constraint handler handles cardinality constraints of the form
21  * \f[
22  * |\mbox{supp}(x)| \leq b
23  * \f]
24  * with integer right-hand side \f$b\f$. Here, \f$|\mbox{supp}(x)|\f$ denotes the number of nonzero entries of the
25  * vector \f$x\f$.
26  *
27  * Note that cardinality constraints generalize special ordered set of type one (SOS1) constraints in which \f$b = 1\f$.
28  *
29  * The implementation of this constraint handler is based on@n
30  * "On the Structure of Linear Programs with Overlapping Cardinality Constraints"@n
31  * T. Fischer and M. E. Pfetsch, Tech. rep., 2016
32  */
33 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 #include <assert.h>
37 
38 #include "scip/cons_cardinality.h"
39 #include "scip/cons_linear.h"
40 #include "scip/cons_knapsack.h"
41 #include <string.h>
42 
43 /* constraint handler properties */
44 #define CONSHDLR_NAME "cardinality"
45 #define CONSHDLR_DESC "cardinality constraint handler"
46 #define CONSHDLR_SEPAPRIORITY 10 /**< priority of the constraint handler for separation */
47 #define CONSHDLR_ENFOPRIORITY 100 /**< priority of the constraint handler for constraint enforcing */
48 #define CONSHDLR_CHECKPRIORITY -10 /**< priority of the constraint handler for checking feasibility */
49 #define CONSHDLR_SEPAFREQ 10 /**< frequency for separating cuts; zero means to separate only in the root node */
50 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
51 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
52  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
53 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in
54  * (-1: no limit) */
55 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
56 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
57 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
58 
59 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
60 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
61 
62 /* branching rules */
63 #define DEFAULT_BRANCHBALANCED FALSE /**< whether to use balanced instead of unbalanced branching */
64 #define DEFAULT_BALANCEDDEPTH 20 /**< maximum depth for using balanced branching (-1: no limit) */
65 #define DEFAULT_BALANCEDCUTOFF 2.0 /**< determines that balanced branching is only used if the branching cut off value
66  * w.r.t. the current LP solution is greater than a given value */
67 
68 /* event handler properties */
69 #define EVENTHDLR_NAME "cardinality"
70 #define EVENTHDLR_DESC "bound change event handler for cardinality constraints"
71 
72 
73 /** constraint data for cardinality constraints */
74 struct SCIP_ConsData
75 {
76  SCIP_CONS* cons; /**< cardinality constraint */
77  int cardval; /**< number of variables that the constraint allows to be nonzero */
78  int nvars; /**< number of variables in the constraint */
79  int maxvars; /**< maximal number of variables (= size of storage) */
80  int ntreatnonzeros; /**< number of variables in constraint that are either known to be nonzero
81  * (because zero is not in variable domain) or may be treated as nonzero */
82  SCIP_EVENTDATA** eventdatascurrent; /**< event datas for current bound change events */
83  SCIP_VAR** eventvarscurrent; /**< event variables for current bound change events */
84  int neventdatascurrent; /**< number of current bound change events */
85  SCIP_EVENTDATA** eventdatas; /**< event data array for bound change events */
86  SCIP_VAR** vars; /**< variables in constraint */
87  SCIP_VAR** indvars; /**< indicator variables that indicate which variables may be treated as
88  * nonzero in cardinality constraint */
89  SCIP_Real* weights; /**< weights determining the order (ascending), or NULL if not used */
90  SCIP_ROW* rowlb; /**< row corresponding to lower bounds, or NULL if not yet created */
91  SCIP_ROW* rowub; /**< row corresponding to upper bounds, or NULL if not yet created */
92 };
93 
94 /** cardinality constraint handler data */
95 struct SCIP_ConshdlrData
96 {
97  SCIP_HASHMAP* varhash; /**< hash map from implied variable to (binary) indicator variable */
98  SCIP_Bool branchbalanced; /**< whether to use balanced instead of unbalanced branching */
99  int balanceddepth; /**< maximum depth for using balanced branching (-1: no limit) */
100  SCIP_Real balancedcutoff; /**< determines that balanced branching is only used if the branching cut off
101  * value w.r.t. the current LP solution is greater than a given value */
102  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
103 };
104 
105 /** event data for bound changes events */
106 struct SCIP_EventData
107 {
108  SCIP_CONSDATA* consdata; /**< cardinality constraint data to process the bound change for */
109  SCIP_VAR* var; /**< implied variable */
110  SCIP_VAR* indvar; /**< indicator variable */
111  unsigned int pos:30; /**< position in constraint */
112  unsigned int varmarked:1; /**< whether implied variable is marked for propagation */
113  unsigned int indvarmarked:1; /**< whether indicator variable is marked for propagation */
114 };
115 
116 /** catches bound change events for a variable and its indicator variable */
117 static
119  SCIP* scip, /**< SCIP data structure */
120  SCIP_EVENTHDLR* eventhdlr, /**< event handler for bound change events */
121  SCIP_CONSDATA* consdata, /**< constraint data */
122  SCIP_VAR* var, /**< implied variable */
123  SCIP_VAR* indvar, /**< indicator variable */
124  int pos, /**< position in constraint */
125  SCIP_EVENTDATA** eventdata /**< pointer to store event data for bound change events */
126  )
127 {
128  assert(eventhdlr != NULL);
129  assert(consdata != NULL);
130  assert(var != NULL);
131  assert(indvar != NULL);
132  assert(pos >= 0);
133 
134  /* create event data of indicator variable */
135  SCIP_CALL( SCIPallocBlockMemory(scip, eventdata) );
136 
137  (*eventdata)->consdata = consdata;
138  (*eventdata)->var = var;
139  (*eventdata)->indvar = indvar;
140  (*eventdata)->varmarked = FALSE;
141  (*eventdata)->indvarmarked = FALSE;
142  (*eventdata)->pos = (unsigned int)pos;
143 
144  /* catch bound change events of each variable */
145  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, *eventdata, NULL) );
146  SCIP_CALL( SCIPcatchVarEvent(scip, indvar, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, *eventdata, NULL) );
147 
148  return SCIP_OKAY;
149 }
150 
151 /** drops bound change events for a variable and its indicator variable */
152 static
154  SCIP* scip, /**< SCIP data structure */
155  SCIP_EVENTHDLR* eventhdlr, /**< event handler for bound change events */
156  SCIP_CONSDATA* consdata, /**< constraint data */
157  SCIP_VAR* var, /**< implied variable */
158  SCIP_VAR* indvar, /**< indicator variable */
159  SCIP_EVENTDATA** eventdata /**< pointer of event data for bound change events */
160  )
161 {
162  assert(eventhdlr != NULL);
163  assert(consdata != NULL);
164  assert(var != NULL);
165  assert(indvar != NULL);
166  assert(eventdata != NULL);
167 
168  /* drop bound change events of each variable */
169  SCIP_CALL( SCIPdropVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, *eventdata, -1) );
170  SCIP_CALL( SCIPdropVarEvent(scip, indvar, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, *eventdata, -1) );
171 
172  /* free event data of indicator variable */
173  SCIPfreeBlockMemory(scip, eventdata);
174  *eventdata = NULL;
175 
176  return SCIP_OKAY;
177 }
178 
179 /** fix variable in given node to 0 or add constraint if variable is multi-aggregated
180  *
181  * @todo Try to handle multi-aggregated variables as in \ref fixVariableZero() below.
182  */
183 static
185  SCIP* scip, /**< SCIP pointer */
186  SCIP_VAR* var, /**< variable to be fixed to 0 */
187  SCIP_NODE* node, /**< node */
188  SCIP_Bool* infeasible /**< pointer to store if fixing is infeasible */
189  )
190 {
191  /* if variable cannot be nonzero */
192  *infeasible = FALSE;
194  {
195  *infeasible = TRUE;
196  return SCIP_OKAY;
197  }
198 
199  /* if variable is multi-aggregated */
201  {
202  SCIP_CONS* cons;
203  SCIP_Real val;
204 
205  val = 1.0;
206 
207  if( !SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || !SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
208  {
209  SCIPdebugMsg(scip, "creating constraint to force multi-aggregated variable <%s> to 0.\n", SCIPvarGetName(var));
210 
211  /* we have to insert a local constraint var = 0 */
212  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "branch", 1, &var, &val, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
213  TRUE, FALSE, FALSE, FALSE, FALSE) );
214  SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) );
215  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
216  }
217  }
218  else
219  {
220  if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
221  {
222  SCIP_CALL( SCIPchgVarLbNode(scip, node, var, 0.0) );
223  }
224  if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
225  {
226  SCIP_CALL( SCIPchgVarUbNode(scip, node, var, 0.0) );
227  }
228  }
229 
230  return SCIP_OKAY;
231 }
232 
233 /** try to fix variable to 0
234  *
235  * Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
236  * \f[
237  * x = \sum_{i=1}^n \alpha_i x_i + c,
238  * \f]
239  * we can express the fixing \f$x = 0\f$ by fixing all \f$x_i\f$ to 0 if \f$c = 0\f$ and the lower bounds of \f$x_i\f$
240  * are nonnegative if \f$\alpha_i > 0\f$ or the upper bounds are nonpositive if \f$\alpha_i < 0\f$.
241  */
242 static
244  SCIP* scip, /**< SCIP pointer */
245  SCIP_VAR* var, /**< variable to be fixed to 0*/
246  SCIP_Bool* infeasible, /**< if fixing is infeasible */
247  SCIP_Bool* tightened /**< if fixing was performed */
248  )
249 {
250  assert(scip != NULL);
251  assert(var != NULL);
252  assert(infeasible != NULL);
253  assert(tightened != NULL);
254 
255  *infeasible = FALSE;
256  *tightened = FALSE;
257 
259  {
260  SCIP_Real aggrconst;
261 
262  /* if constant is 0 */
263  aggrconst = SCIPvarGetMultaggrConstant(var);
264  if( SCIPisZero(scip, aggrconst) )
265  {
266  SCIP_VAR** aggrvars;
267  SCIP_Real* aggrvals;
268  SCIP_Bool allnonnegative = TRUE;
269  int naggrvars;
270  int i;
271 
273 
274  /* check whether all variables are "nonnegative" */
275  naggrvars = SCIPvarGetMultaggrNVars(var);
276  aggrvars = SCIPvarGetMultaggrVars(var);
277  aggrvals = SCIPvarGetMultaggrScalars(var);
278  for( i = 0; i < naggrvars; ++i )
279  {
280  if( (SCIPisPositive(scip, aggrvals[i]) && SCIPisNegative(scip, SCIPvarGetLbLocal(aggrvars[i]))) ||
281  (SCIPisNegative(scip, aggrvals[i]) && SCIPisPositive(scip, SCIPvarGetUbLocal(aggrvars[i]))) )
282  {
283  allnonnegative = FALSE;
284  break;
285  }
286  }
287 
288  if( allnonnegative )
289  {
290  /* all variables are nonnegative -> fix variables */
291  for( i = 0; i < naggrvars; ++i )
292  {
293  SCIP_Bool fixed;
294  SCIP_CALL( SCIPfixVar(scip, aggrvars[i], 0.0, infeasible, &fixed) );
295  if( *infeasible )
296  return SCIP_OKAY;
297  *tightened = *tightened || fixed;
298  }
299  }
300  }
301  }
302  else
303  {
304  SCIP_CALL( SCIPfixVar(scip, var, 0.0, infeasible, tightened) );
305  }
306 
307  return SCIP_OKAY;
308 }
309 
310 /** add lock on variable */
311 static
313  SCIP* scip, /**< SCIP data structure */
314  SCIP_CONS* cons, /**< constraint */
315  SCIP_VAR* var, /**< variable */
316  SCIP_VAR* indvar /**< indicator variable */
317  )
318 {
319  assert(scip != NULL);
320  assert(cons != NULL);
321  assert(var != NULL);
322 
323  /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */
324  SCIP_CALL( SCIPlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)),
325  SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var))) );
326  SCIP_CALL( SCIPlockVarCons(scip, indvar, cons, TRUE, TRUE) );
327 
328  return SCIP_OKAY;
329 }
330 
331 /* remove lock on variable */
332 static
334  SCIP* scip, /**< SCIP data structure */
335  SCIP_CONS* cons, /**< constraint */
336  SCIP_VAR* var, /**< variable */
337  SCIP_VAR* indvar /**< indicator variable */
338  )
339 {
340  assert(scip != NULL);
341  assert(cons != NULL);
342  assert(var != NULL);
343 
344  /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */
345  SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)),
346  SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var))) );
347  SCIP_CALL( SCIPunlockVarCons(scip, indvar, cons, TRUE, TRUE) );
348 
349  return SCIP_OKAY;
350 }
351 
352 /** ensures that the vars and weights array can store at least num entries */
353 static
355  SCIP* scip, /**< SCIP data structure */
356  SCIP_CONSDATA* consdata, /**< constraint data */
357  int num, /**< minimum number of entries to store */
358  SCIP_Bool reserveweights /**< whether the weights array is handled */
359  )
360 {
361  assert(consdata != NULL);
362  assert(consdata->nvars <= consdata->maxvars);
363 
364  if( num > consdata->maxvars )
365  {
366  int newsize;
367 
368  newsize = SCIPcalcMemGrowSize(scip, num);
369  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->maxvars, newsize) );
370  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->indvars, consdata->maxvars, newsize) );
371  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdatas, consdata->maxvars, newsize) );
372  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*consdata->maxvars, 4*newsize) );/*lint !e647*/
373  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*consdata->maxvars, 4*newsize) );/*lint !e647*/
374 
375  if ( reserveweights )
376  {
377  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->maxvars, newsize) );
378  }
379  consdata->maxvars = newsize;
380  }
381  assert(num <= consdata->maxvars);
382 
383  return SCIP_OKAY;
384 }
385 
386 /** handle new variable that was added to the constraint
387  *
388  * We perform the following steps:
389  *
390  * - catch bound change events of variable.
391  * - update rounding locks of variable.
392  * - don't allow multiaggregation of variable, since this cannot be handled by branching in the current implementation
393  * - update lower and upper bound row, i.e., the linear representations of the cardinality constraints
394  */
395 static
397  SCIP* scip, /**< SCIP data structure */
398  SCIP_CONS* cons, /**< constraint */
399  SCIP_CONSDATA* consdata, /**< constraint data */
400  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
401  SCIP_VAR* var, /**< variable */
402  SCIP_VAR* indvar, /**< indicator variable to indicate whether variable may be treated as
403  * nonzero in cardinality constraint */
404  int pos, /**< position in constraint */
405  SCIP_Bool transformed, /**< whether original variable was transformed */
406  SCIP_EVENTDATA** eventdata /**< pointer to store event data for bound change events */
407  )
408 {
409  assert(scip != NULL);
410  assert(cons != NULL);
411  assert(consdata != NULL);
412  assert(conshdlrdata != NULL);
413  assert(var != NULL);
414 
415  /* if we are in transformed problem, catch the variable's events */
416  if( transformed )
417  {
418  /* catch bound change events of variable */
419  SCIP_CALL( catchVarEventCardinality(scip, conshdlrdata->eventhdlr, consdata, var, indvar, pos, eventdata) );
420  assert(eventdata != NULL );
421 
422  /* if the variable is fixed to nonzero */
423  assert(consdata->ntreatnonzeros >= 0 );
424  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvar), 1.0) )
425  ++consdata->ntreatnonzeros;
426  }
427 
428  /* branching on multiaggregated variables does not seem to work well, so avoid it */
429  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, indvar) );
430 
431  /* install the rounding locks for the new variable */
432  SCIP_CALL( lockVariableCardinality(scip, cons, var, indvar) );
433 
434  /* add the new coefficient to the upper bound LP row, if necessary */
435  if( consdata->rowub != NULL && !SCIPisInfinity(scip, SCIPvarGetUbGlobal(var))
436  && !SCIPisZero(scip, SCIPvarGetUbGlobal(var)) )
437  {
438  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rowub, var, 1.0/SCIPvarGetUbGlobal(var)) );
439  }
440 
441  /* add the new coefficient to the lower bound LP row, if necessary */
442  if( consdata->rowlb != NULL && !SCIPisInfinity(scip, SCIPvarGetLbGlobal(var))
443  && !SCIPisZero(scip, SCIPvarGetLbGlobal(var)) )
444  {
445  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rowlb, var, 1.0/SCIPvarGetLbGlobal(var)) );
446  }
447 
448  return SCIP_OKAY;
449 }
450 
451 /** adds a variable to a cardinality constraint, at position given by weight - ascending order */
452 static
454  SCIP* scip, /**< SCIP data structure */
455  SCIP_CONS* cons, /**< constraint */
456  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
457  SCIP_VAR* var, /**< variable to add to the constraint */
458  SCIP_VAR* indvar, /**< indicator variable to indicate whether variable may be treated as nonzero
459  * in cardinality constraint (or NULL) */
460  SCIP_Real weight /**< weight to determine position */
461  )
462 {
463  SCIP_EVENTDATA* eventdata = NULL;
464  SCIP_CONSDATA* consdata;
465  SCIP_Bool transformed;
466  int pos;
467 
468  assert(var != NULL);
469  assert(cons != NULL);
470  assert(conshdlrdata != NULL);
471 
472  consdata = SCIPconsGetData(cons);
473  assert(consdata != NULL );
474 
475  if( consdata->weights == NULL && consdata->maxvars > 0 )
476  {
477  SCIPerrorMessage("cannot add variable to cardinality constraint <%s> that does not contain weights.\n",
478  SCIPconsGetName(cons));
479  return SCIP_INVALIDCALL;
480  }
481 
482  /* check indicator variable */
483  if( indvar == NULL )
484  {
485  if( conshdlrdata->varhash == NULL )
486  {
487  /* set up hash map */
488  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) );
489  }
490 
491  /* check whether an indicator variable already exists for implied variable */
492  if( SCIPhashmapExists(conshdlrdata->varhash, var) )
493  {
494  assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var) != NULL);
495  indvar = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var);
496  assert(indvar != NULL);
497  }
498  else
499  {
500  /* if implied variable is binary, then it is also not necessary to create an indicator variable */
501  if( SCIPvarIsBinary(var) )
502  indvar = var;
503  else
504  {
505  char varname[SCIP_MAXSTRLEN];
506  SCIP_VAR* newvar;
507 
508  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(var));
509  SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE,
510  NULL, NULL, NULL, NULL, NULL) );
511  SCIP_CALL( SCIPaddVar(scip, newvar) );
512  indvar = newvar;
513 
514  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
515  }
516  assert(indvar != NULL);
517 
518  /* insert implied variable to hash map */
519  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, var, (void*) indvar) );/*lint !e571*/
520  assert(indvar == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var));
521  assert(SCIPhashmapExists(conshdlrdata->varhash, var));
522  }
523  }
524 
525  /* are we in the transformed problem? */
526  transformed = SCIPconsIsTransformed(cons);
527 
528  /* always use transformed variables in transformed constraints */
529  if( transformed )
530  {
531  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
532  SCIP_CALL( SCIPgetTransformedVar(scip, indvar, &indvar) );
533  }
534  assert(var != NULL);
535  assert(indvar != NULL);
536  assert(transformed == SCIPvarIsTransformed(var));
537  assert(transformed == SCIPvarIsTransformed(indvar));
538 
539  /* ensure that the new information can be storend in the constraint data */
540  SCIP_CALL( consdataEnsurevarsSizeCardinality(scip, consdata, consdata->nvars + 1, TRUE) );
541  assert(consdata->weights != NULL);
542  assert(consdata->maxvars >= consdata->nvars+1);
543 
544  /* move other variables, if necessary */
545  for( pos = consdata->nvars; pos >= 1; --pos )
546  {
547  if( consdata->weights[pos-1] > weight )
548  {
549  consdata->vars[pos] = consdata->vars[pos-1];
550  consdata->indvars[pos] = consdata->indvars[pos-1];
551  consdata->eventdatas[pos] = consdata->eventdatas[pos-1];
552  consdata->weights[pos] = consdata->weights[pos-1];
553 
554  if( consdata->eventdatas[pos] != NULL )
555  {
556  consdata->eventdatas[pos]->pos = (unsigned int)pos;
557  }
558  }
559  else
560  break;
561  }
562  assert(0 <= pos && pos <= consdata->nvars);
563 
564  /* handle the new variable */
565  SCIP_CALL( handleNewVariableCardinality(scip, cons, consdata, conshdlrdata, var, indvar, pos, transformed, &eventdata) );
566  assert(! transformed || eventdata != NULL);
567 
568  /* insert variable */
569  consdata->vars[pos] = var;
570  consdata->indvars[pos] = indvar;
571  consdata->eventdatas[pos] = eventdata;
572  consdata->weights[pos] = weight;
573  ++consdata->nvars;
574 
575  return SCIP_OKAY;
576 }
577 
578 /** appends a variable to a cardinality constraint */
579 static
581  SCIP* scip, /**< SCIP data structure */
582  SCIP_CONS* cons, /**< constraint */
583  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
584  SCIP_VAR* var, /**< variable to add to the constraint */
585  SCIP_VAR* indvar /**< indicator variable to indicate whether variable may be treated as nonzero
586  * in cardinality constraint */
587  )
588 {
589  SCIP_EVENTDATA* eventdata = NULL;
590  SCIP_CONSDATA* consdata;
591  SCIP_Bool transformed;
592 
593  assert(var != NULL);
594  assert(cons != NULL);
595  assert(conshdlrdata != NULL);
596 
597  consdata = SCIPconsGetData(cons);
598  assert(consdata != NULL);
599 
600  /* check indicator variable */
601  if( indvar == NULL )
602  {
603  if( conshdlrdata->varhash == NULL )
604  {
605  /* set up hash map */
606  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) );
607  }
608 
609  /* check whether an indicator variable already exists for implied variable */
610  if( SCIPhashmapExists(conshdlrdata->varhash, var) )
611  {
612  assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var) != NULL);
613  indvar = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var);
614  assert(indvar != NULL);
615  }
616  else
617  {
618  /* if implied variable is binary, then it is also not necessary to create an indicator variable */
619  if( SCIPvarIsBinary(var) )
620  indvar = var;
621  else
622  {
623  char varname[SCIP_MAXSTRLEN];
624  SCIP_VAR* newvar;
625 
626  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(var));
627  SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE,
628  NULL, NULL, NULL, NULL, NULL) );
629  SCIP_CALL( SCIPaddVar(scip, newvar) );
630  indvar = newvar;
631 
632  SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
633  }
634  assert(indvar != NULL);
635 
636  /* insert implied variable to hash map */
637  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, var, (void*) indvar) );/*lint !e571*/
638  assert(indvar == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, var));
639  assert(SCIPhashmapExists(conshdlrdata->varhash, var));
640  }
641  }
642 
643  /* are we in the transformed problem? */
644  transformed = SCIPconsIsTransformed(cons);
645 
646  /* always use transformed variables in transformed constraints */
647  if( transformed )
648  {
649  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
650  SCIP_CALL( SCIPgetTransformedVar(scip, indvar, &indvar) );
651  }
652  assert(var != NULL);
653  assert(indvar != NULL);
654  assert(transformed == SCIPvarIsTransformed(var));
655  assert(transformed == SCIPvarIsTransformed(indvar));
656 
657  /* ensure that the new information can be stored in the constraint data */
658  SCIP_CALL( consdataEnsurevarsSizeCardinality(scip, consdata, consdata->nvars + 1, FALSE) );
659 
660  /* handle the new variable */
661  SCIP_CALL( handleNewVariableCardinality(scip, cons, consdata, conshdlrdata, var, indvar, consdata->nvars, transformed,
662  &eventdata) );
663  assert(!transformed || eventdata != NULL);
664 
665  /* insert variable */
666  consdata->vars[consdata->nvars] = var;
667  consdata->indvars[consdata->nvars] = indvar;
668  consdata->eventdatas[consdata->nvars] = eventdata;
669 
670  if( consdata->weights != NULL && consdata->nvars > 0 )
671  consdata->weights[consdata->nvars] = consdata->weights[consdata->nvars-1] + 1.0;
672  ++consdata->nvars;
673 
674  assert(consdata->weights != NULL || consdata->nvars > 0);
675 
676  return SCIP_OKAY;
677 }
678 
679 /** deletes a variable from a cardinality constraint */
680 static
682  SCIP* scip, /**< SCIP data structure */
683  SCIP_CONS* cons, /**< constraint */
684  SCIP_CONSDATA* consdata, /**< constraint data */
685  SCIP_EVENTHDLR* eventhdlr, /**< corresponding event handler */
686  int pos /**< position of variable in array */
687  )
688 { /*lint --e{679}*/
689  int j;
690 
691  assert(0 <= pos && pos < consdata->nvars);
692 
693  /* remove lock of variable */
694  SCIP_CALL( unlockVariableCardinality(scip, cons, consdata->vars[pos], consdata->indvars[pos]) );
695 
696  /* drop events on indicator variable and implied variable */
697  SCIP_CALL( dropVarEventCardinality(scip, eventhdlr, consdata, consdata->vars[pos], consdata->indvars[pos],
698  &consdata->eventdatas[pos]) );
699 
700  /* update number of variables that may be treated as nonzero */
701  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->indvars[pos]), 1.0) )
702  --(consdata->ntreatnonzeros);
703 
704  /* delete variable - need to copy since order is important */
705  for( j = pos; j < consdata->nvars-1; ++j )
706  {
707  consdata->vars[j] = consdata->vars[j+1];
708  consdata->indvars[j] = consdata->indvars[j+1];
709  consdata->eventdatas[j] = consdata->eventdatas[j+1];
710  if( consdata->weights != NULL )
711  consdata->weights[j] = consdata->weights[j+1];
712 
713  consdata->eventdatas[j]->pos = (unsigned int)j;
714  }
715  --consdata->nvars;
716 
717  return SCIP_OKAY;
718 }
719 
720 /** for each indicator variable sets solution to 1.0 if the solution value of the implied variable is nonzero */
721 static
723  SCIP* scip, /**< SCIP pointer */
724  SCIP_CONS** conss, /**< constraints */
725  int nconss, /**< number of constraints */
726  SCIP_SOL* sol, /**< solution to be enforced (or NULL) */
727  SCIP_SOL* primsol /**< primal solution */
728  )
729 {
730  SCIP_CONSDATA* consdata;
731  SCIP_VAR** indvars;
732  SCIP_VAR** vars;
733  int nvars;
734  int c;
735 
736  /* check each constraint */
737  for( c = 0; c < nconss; ++c )
738  {
739  SCIP_CONS* cons;
740  int j;
741 
742  cons = conss[c];
743  assert(cons != NULL);
744  consdata = SCIPconsGetData(cons);
745  assert(consdata != NULL);
746 
747  nvars = consdata->nvars;
748  vars = consdata->vars;
749  indvars = consdata->indvars;
750 
751  for( j = 0; j < nvars; ++j )
752  {
753  if( SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[j])) )
754  {
755  SCIP_CALL( SCIPsetSolVal(scip, primsol, indvars[j], 0.0) );
756  }
757  else
758  {
759  SCIP_CALL( SCIPsetSolVal(scip, primsol, indvars[j], 1.0) );
760  }
761  }
762  }
763 
764  return SCIP_OKAY;
765 }
766 
767 /** unmark variables that are marked for propagation */
768 static
770  SCIP_CONSDATA* consdata /**< constraint data */
771  )
772 {
773  SCIP_EVENTDATA** eventdatas;
774  int nvars;
775  int j;
776 
777  eventdatas = consdata->eventdatas;
778  nvars = consdata->nvars;
779  assert(eventdatas != NULL);
780 
781  for( j = 0; j < nvars; ++j )
782  {
783  SCIP_EVENTDATA* eventdata;
784 
785  eventdata = eventdatas[j];
786  eventdata->varmarked = FALSE;
787  eventdata->indvarmarked = FALSE;
788  }
789 
790  return SCIP_OKAY;
791 }
792 
793 /** perform one presolving round
794  *
795  * We perform the following presolving steps:
796  *
797  * - If the bounds of some variable force it to be nonzero, we can
798  * fix all other variables to zero and remove the cardinality constraints
799  * that contain it.
800  * - If a variable is fixed to zero, we can remove the variable.
801  * - If a variable appears twice, it can be fixed to 0.
802  * - We substitute appregated variables.
803  */
804 static
806  SCIP* scip, /**< SCIP pointer */
807  SCIP_CONS* cons, /**< constraint */
808  SCIP_CONSDATA* consdata, /**< constraint data */
809  SCIP_EVENTHDLR* eventhdlr, /**< event handler */
810  SCIP_Bool* cutoff, /**< whether a cutoff happened */
811  SCIP_Bool* success, /**< whether we performed a successful reduction */
812  int* ndelconss, /**< number of deleted constraints */
813  int* nupgdconss, /**< number of upgraded constraints */
814  int* nfixedvars, /**< number of fixed variables */
815  int* nremovedvars /**< number of variables removed */
816  )
817 {
818  SCIP_VAR** indvars;
819  SCIP_VAR** vars;
820  SCIP_Bool allvarsbinary;
821  SCIP_Bool infeasible;
822  SCIP_Bool fixed;
823  int j;
824 
825  assert(scip != NULL);
826  assert(cons != NULL);
827  assert(consdata != NULL);
828  assert(eventhdlr != NULL);
829  assert(cutoff != NULL);
830  assert(success != NULL);
831  assert(ndelconss != NULL);
832  assert(nfixedvars != NULL);
833  assert(nremovedvars != NULL);
834 
835  *cutoff = FALSE;
836  *success = FALSE;
837 
838  SCIPdebugMsg(scip, "Presolving cardinality constraint <%s>.\n", SCIPconsGetName(cons) );
839 
840  /* reset number of events stored for propagation, since presolving already performs a
841  * complete propagation of all variables */
842  consdata->neventdatascurrent = 0;
844 
845  j = 0;
846  allvarsbinary = TRUE;
847  vars = consdata->vars;
848  indvars = consdata->indvars;
849 
850  /* check for variables fixed to 0 and bounds that fix a variable to be nonzero */
851  while ( j < consdata->nvars )
852  {
853  int l;
854  SCIP_VAR* var;
855  SCIP_VAR* oldvar;
856  SCIP_VAR* indvar;
857  SCIP_Real lb;
858  SCIP_Real ub;
859  SCIP_Real indlb;
860  SCIP_Real indub;
861  SCIP_Real scalar;
862  SCIP_Real constant;
863 
864  scalar = 1.0;
865  constant = 0.0;
866 
867  /* check for aggregation: if the constant is zero the variable is zero iff the aggregated
868  * variable is 0 */
869  var = vars[j];
870  indvar = indvars[j];
871  oldvar = var;
872  SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) );
873 
874  /* if constant is zero and we get a different variable, substitute variable */
875  if( SCIPisZero(scip, constant) && !SCIPisZero(scip, scalar) && var != vars[j] )
876  {
877  SCIPdebugMsg(scip, "substituted variable <%s> by <%s>.\n", SCIPvarGetName(vars[j]), SCIPvarGetName(var));
878 
879  /* we reuse the same indicator variable for the new variable */
880  SCIP_CALL( dropVarEventCardinality(scip, eventhdlr, consdata, consdata->vars[j], consdata->indvars[j],
881  &consdata->eventdatas[j]) );
882  SCIP_CALL( catchVarEventCardinality(scip, eventhdlr, consdata, var, consdata->indvars[j], j,
883  &consdata->eventdatas[j]) );
884  assert(consdata->eventdatas[j] != NULL);
885 
886  /* change the rounding locks */
887  SCIP_CALL( unlockVariableCardinality(scip, cons, consdata->vars[j], consdata->indvars[j]) );
888  SCIP_CALL( lockVariableCardinality(scip, cons, var, consdata->indvars[j]) );
889 
890  /* update event data */
891  consdata->eventdatas[j]->var = var;
892 
893  vars[j] = var;
894  }
895  assert(var == vars[j]);
896 
897  /* check whether the variable appears again later */
898  for( l = j+1; l < consdata->nvars; ++l )
899  {
900  if( var == vars[l] || oldvar == vars[l] )
901  {
902  SCIPdebugMsg(scip, "variable <%s> appears twice in constraint <%s>.\n", SCIPvarGetName(vars[j]),
903  SCIPconsGetName(cons));
904  return SCIP_INVALIDDATA;
905  }
906  }
907 
908  /* get bounds of variable */
909  lb = SCIPvarGetLbLocal(var);
910  ub = SCIPvarGetUbLocal(var);
911 
912  /* if the variable is fixed to nonzero */
913  if( SCIPisFeasPositive(scip, lb) || SCIPisFeasNegative(scip, ub) )
914  {
915  assert(SCIPvarIsBinary(indvar));
916 
917  /* fix (binary) indicator variable to 1.0 (the cardinality constraint will then be modified below) */
918  SCIP_CALL( SCIPfixVar(scip, indvar, 1.0, &infeasible, &fixed) );
919  if( infeasible )
920  {
921  *cutoff = TRUE;
922  return SCIP_OKAY;
923  }
924 
925  if( fixed )
926  {
927  SCIPdebugMsg(scip, "fixed binary variable <%s> to 1.0.\n", SCIPvarGetName(indvar));
928  ++(*nfixedvars);
929  }
930  }
931 
932  /* if the variable is fixed to 0 */
933  if( SCIPisFeasZero(scip, lb) && SCIPisFeasZero(scip, ub) )
934  {
935  assert(SCIPvarIsBinary(indvar));
936 
937  /* fix (binary) indicator variable to 0.0, if possible (the cardinality constraint will then be modified below)
938  * note that an infeasibility implies no cut off */
939  SCIP_CALL( SCIPfixVar(scip, indvar, 0.0, &infeasible, &fixed) );
940  if( fixed )
941  {
942  SCIPdebugMsg(scip, "fixed binary variable <%s> to 0.0.\n", SCIPvarGetName(indvar));
943  ++(*nfixedvars);
944  }
945  }
946 
947  /* get bounds of indicator variable */
948  indlb = SCIPvarGetLbLocal(indvar);
949  indub = SCIPvarGetUbLocal(indvar);
950 
951  /* if the variable may be treated as nonzero */
952  if( SCIPisFeasEQ(scip, indlb, 1.0) )
953  {
954  assert(indub == 1.0);
955 
956  /* modify row and delete variable */
957  SCIP_CALL( deleteVarCardinality(scip, cons, consdata, eventhdlr, j) );
958  SCIPdebugMsg(scip, "deleting variable <%s> from constraint <%s>, since it may be treated as nonzero.\n",
959  SCIPvarGetName(var), SCIPconsGetName(cons));
960  --(consdata->cardval);
961  ++(*nremovedvars);
962  }
963  /* if the indicator variable is fixed to 0 */
964  else if( SCIPisFeasEQ(scip, indub, 0.0) )
965  {
966  assert(indlb == 0.0);
967 
968  /* fix variable to 0.0 */
969  SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
970  if( infeasible )
971  {
972  *cutoff = TRUE;
973  return SCIP_OKAY;
974  }
975  if( fixed )
976  {
977  SCIPdebugMsg(scip, "fixed variable <%s> to 0.0.\n", SCIPvarGetName(var));
978  ++(*nfixedvars);
979  }
980 
981  /* delete variable */
982  SCIP_CALL( deleteVarCardinality(scip, cons, consdata, eventhdlr, j) );
983  SCIPdebugMsg(scip, "deleting variable <%s> from constraint <%s>, since it is fixed to 0.\n", SCIPvarGetName(var),
984  SCIPconsGetName(cons));
985  ++(*nremovedvars);
986  }
987  else
988  {
989  /* check whether all variables are binary */
990  if( !SCIPvarIsBinary(var) )
991  allvarsbinary = FALSE;
992 
993  ++j;
994  }
995  }
996 
997  /* if the cardinality value is smaller than 0, then the problem is infeasible */
998  if( consdata->cardval < 0 )
999  {
1000  SCIPdebugMsg(scip, "The problem is infeasible: more variables have bounds that keep them from being 0 than allowed.\n");
1001 
1002  *cutoff = TRUE;
1003  return SCIP_OKAY;
1004  }
1005  /* else if the cardinality value is 0 */
1006  else if( consdata->cardval == 0 )
1007  {
1008  /* fix all variables of the constraint to 0 */
1009  for( j = 0; j < consdata->nvars; ++j )
1010  {
1011  SCIP_CALL( SCIPfixVar(scip, consdata->vars[j], 0.0, &infeasible, &fixed) );
1012  if( infeasible )
1013  {
1014  *cutoff = TRUE;
1015  return SCIP_OKAY;
1016  }
1017  if( fixed )
1018  {
1019  SCIPdebugMsg(scip, "fixed variable <%s> to 0.0.\n", SCIPvarGetName(consdata->vars[j]));
1020  ++(*nfixedvars);
1021  }
1022  }
1023  }
1024 
1025  /* if the cardinality constraint is redundant */
1026  if( consdata->nvars <= consdata->cardval )
1027  {
1028  SCIPdebugMsg(scip, "Deleting cardinality constraint <%s> with <%d> variables and cardinality value <%d>.\n",
1029  SCIPconsGetName(cons), consdata->nvars, consdata->cardval);
1030 
1031  /* delete constraint */
1032  assert(!SCIPconsIsModifiable(cons));
1033  SCIP_CALL( SCIPdelCons(scip, cons) );
1034  ++(*ndelconss);
1035  *success = TRUE;
1036  return SCIP_OKAY;
1037  }
1038  else
1039  {
1040  /* if all variables are binary create a knapsack constraint */
1041  if( allvarsbinary )
1042  {
1043  SCIP_CONS* knapsackcons;
1044  SCIP_Longint* vals;
1045 
1046  SCIP_CALL( SCIPallocBufferArray(scip, &vals, consdata->nvars) );
1047  for( j = 0; j < consdata->nvars; ++j )
1048  vals[j] = 1;
1049 
1050  /* create, add, and release the knapsack constraint */
1051  SCIP_CALL( SCIPcreateConsKnapsack(scip, &knapsackcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars,
1052  vals, (SCIP_Longint) consdata->cardval, SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons),
1055  SCIPconsIsStickingAtNode(cons)) );/*lint !e524*/
1056  SCIP_CALL( SCIPaddCons(scip, knapsackcons) );
1057  SCIP_CALL( SCIPreleaseCons(scip, &knapsackcons) );
1058 
1059  SCIPfreeBufferArray(scip, &vals);
1060 
1061  SCIPdebugMsg(scip, "Upgrading cardinality constraint <%s> to knapsack constraint.\n", SCIPconsGetName(cons));
1062 
1063  /* remove the cardinality constraint globally */
1064  assert(!SCIPconsIsModifiable(cons));
1065  SCIP_CALL( SCIPdelCons(scip, cons) );
1066  ++(*nupgdconss);
1067  *success = TRUE;
1068  }
1069  }
1070 
1071  return SCIP_OKAY;
1072 }
1073 
1074 /** propagates a cardinality constraint and its variables
1075  *
1076  * The number 'ntreatnonzeros' that is assigned to the constraint data returns the number of variables that are either
1077  * known to be nonzero or can be treated as nonzero. We say that a variable is known to be nonzero, if zero is outside
1078  * the domain of this variable. A variable can be treated as nonzero, if its corresponding indicator variable 'indvar' is
1079  * fixed to 1.0, e.g., by branching.
1080  *
1081  * We perform the following propagation steps:
1082  *
1083  * - if the number 'ntreatnonzeros' is greater than the cardinality value of the constraint, then the current subproblem
1084  * is marked as infeasible.
1085  * - if the cardinality constraint is saturated, i.e., the number 'ntreatnonzeros' is equal to the cardinality value of
1086  * the constraint, then fix all the other variables of the constraint to zero.
1087  * - remove the cardinality constraint locally if all variables are either fixed to zero or can be treated as nonzero.
1088  * - if a (binary) indicator variable is fixed to zero, then fix the corresponding implied variable to zero.
1089  * - if zero is outside of the domain of an implied variable, then fix the corresponding indicator variable to one.
1090  */
1091 static
1093  SCIP* scip, /**< SCIP pointer */
1094  SCIP_CONS* cons, /**< constraint */
1095  SCIP_CONSDATA* consdata, /**< constraint data */
1096  SCIP_Bool* cutoff, /**< whether a cutoff happened */
1097  int* nchgdomain /**< number of domain changes */
1098  )
1099 {
1100  assert(scip != NULL);
1101  assert(cons != NULL);
1102  assert(consdata != NULL);
1103  assert(cutoff != NULL);
1104  assert(nchgdomain != NULL);
1105 
1106  *cutoff = FALSE;
1107 
1108  /* if more variables may be treated as nonzero than allowed */
1109  if( consdata->ntreatnonzeros > consdata->cardval )
1110  {
1111  SCIPdebugMsg(scip, "the node is infeasible, more than %d variables are fixed to be nonzero.\n", consdata->cardval);
1112  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1113  *cutoff = TRUE;
1114 
1115  return SCIP_OKAY;
1116  }
1117 
1118  /* if number of nonzeros is saturated */
1119  if( consdata->ntreatnonzeros == consdata->cardval )
1120  {
1121  SCIP_VAR** vars;
1122  SCIP_VAR** indvars;
1123  SCIP_Bool infeasible;
1124  SCIP_Bool tightened;
1125  SCIP_Bool allvarfixed;
1126  int nvars;
1127  int cnt = 0;
1128  int j;
1129 
1130  nvars = consdata->nvars;
1131  vars = consdata->vars;
1132  indvars = consdata->indvars;
1133  assert(vars != NULL);
1134  assert(indvars != NULL);
1135 
1136  /* fix free variables to zero */
1137  allvarfixed = TRUE;
1138  for( j = 0; j < nvars; ++j )
1139  {
1140  /* if variable is implied to be treated as nonzero */
1141  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvars[j]), 1.0) )
1142  ++cnt;
1143  /* else fix variable to zero if not done already */
1144  else
1145  {
1146  SCIP_VAR* var;
1147 
1148  var = vars[j];
1149 
1150  /* fix variable */
1152  {
1153  SCIP_CALL( fixVariableZero(scip, var, &infeasible, &tightened) );
1154  if( infeasible )
1155  {
1156  SCIPdebugMsg(scip, "the node is infeasible, more than %d variables are fixed to be nonzero.\n",
1157  consdata->cardval);
1158  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1159  *cutoff = TRUE;
1160 
1161  return SCIP_OKAY;
1162  }
1163 
1164  if( tightened )
1165  {
1166  SCIPdebugMsg(scip, "fixed variable <%s> to 0, since constraint <%s> with cardinality value %d is \
1167  saturated.\n", SCIPvarGetName(var), SCIPconsGetName(cons), consdata->cardval);
1168  ++(*nchgdomain);
1169  }
1170  else
1171  allvarfixed = FALSE;
1172  }
1173  }
1174  }
1175  assert(cnt == consdata->ntreatnonzeros);
1176 
1177  /* reset constraint age counter */
1178  if( *nchgdomain > 0 )
1179  {
1180  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1181  }
1182 
1183  /* delete constraint locally */
1184  if( allvarfixed )
1185  {
1186  assert(!SCIPconsIsModifiable(cons));
1187  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
1188 
1189  return SCIP_OKAY;
1190  }
1191  }
1192 
1193  /* if relevant bound change events happened */
1194  if( consdata->neventdatascurrent > 0 )
1195  {
1196  SCIP_EVENTDATA** eventdatas;
1197  SCIP_VAR** eventvars;
1198  int neventdatas;
1199  int j;
1200 
1201  neventdatas = consdata->neventdatascurrent;
1202  eventvars = consdata->eventvarscurrent;
1203  eventdatas = consdata->eventdatascurrent;
1204  assert(eventdatas != NULL && eventvars != NULL);
1205 
1206  for( j = 0; j < neventdatas; ++j )
1207  {
1208  SCIP_EVENTDATA* eventdata;
1209  SCIP_Bool infeasible;
1210  SCIP_Bool tightened;
1211  SCIP_VAR* var;
1212 
1213  eventdata = eventdatas[j];
1214  var = eventvars[j];
1215  assert(var != NULL && eventdata != NULL);
1216  assert(eventdata->var != NULL);
1217  assert(eventdata->indvar != NULL);
1218  assert(var == eventdata->var || var == eventdata->indvar);
1219  assert(SCIPvarIsBinary(eventdata->indvar));
1220 
1221  /* if variable is an indicator variable */
1222  if( eventdata->indvar == var )
1223  {
1224  assert(eventdata->indvarmarked);
1225 
1226  /* if variable is fixed to zero */
1227  if( SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
1228  {
1229  SCIP_VAR* implvar;
1230 
1231  implvar = eventdata->var;
1232 
1233  /* fix implied variable to zero if not done already */
1234  if( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(implvar)) ||
1235  SCIPisFeasPositive(scip, SCIPvarGetUbLocal(implvar)) )
1236  {
1237  SCIP_CALL( fixVariableZero(scip, implvar, &infeasible, &tightened) );
1238 
1239  if( infeasible )
1240  {
1241  SCIPdebugMsg(scip, "the node is infeasible, indicator variable %s is fixed to zero although implied "
1242  "variable %s is nonzero.\n", SCIPvarGetName(var), SCIPvarGetName(implvar));
1243  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1244  *cutoff = TRUE;
1245 
1246  return SCIP_OKAY;
1247  }
1248 
1249  if( tightened )
1250  {
1251  SCIPdebugMsg(scip, "fixed variable <%s> to 0, since indicator variable %s is 0.\n",
1252  SCIPvarGetName(implvar), SCIPvarGetName(var));
1253  ++(*nchgdomain);
1254  }
1255  }
1256  }
1257  eventdata->indvarmarked = FALSE;
1258  }
1259  /* else if variable is an implied variable */
1260  else
1261  {
1262  assert(eventdata->var == var);
1263  assert(eventdata->varmarked);
1264 
1265  /* if variable is is nonzero */
1267  {
1268  SCIP_VAR* indvar;
1269 
1270  indvar = eventdata->indvar;
1271  assert(SCIPvarIsBinary(indvar));
1272 
1273  /* fix indicator variable to 1.0 if not done already */
1274  if( !SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvar), 1.0) )
1275  {
1276  /* if fixing is infeasible */
1277  if( SCIPvarGetUbLocal(indvar) != 1.0 )
1278  {
1279  SCIPdebugMsg(scip, "the node is infeasible, implied variable %s is fixed to nonzero "
1280  "although indicator variable %s is 0.\n", SCIPvarGetName(var), SCIPvarGetName(indvar));
1281  SCIP_CALL( SCIPresetConsAge(scip, cons) );
1282  *cutoff = TRUE;
1283 
1284  return SCIP_OKAY;
1285  }
1286  SCIP_CALL( SCIPchgVarLb(scip, indvar, 1.0) );
1287  SCIPdebugMsg(scip, "fixed variable <%s> to 1.0, since implied variable %s is nonzero.\n",
1288  SCIPvarGetName(indvar), SCIPvarGetName(var));
1289  ++(*nchgdomain);
1290  }
1291  }
1292  eventdata->varmarked = FALSE;
1293  }
1294  }
1295  }
1296  consdata->neventdatascurrent = 0;
1297 
1298  return SCIP_OKAY;
1299 }
1300 
1301 /** apply unbalanced branching (see the function \ref enforceCardinality() for further information) */
1302 static
1304  SCIP* scip, /**< SCIP pointer */
1305  SCIP_SOL* sol, /**< solution to be enforced (or NULL) */
1306  SCIP_CONS* branchcons, /**< cardinality constraint */
1307  SCIP_VAR** vars, /**< variables of constraint */
1308  SCIP_VAR** indvars, /**< indicator variables */
1309  int nvars, /**< number of variables of constraint */
1310  int cardval, /**< cardinality value of constraint */
1311  int branchnnonzero, /**< number of variables that are fixed to be nonzero */
1312  int branchpos /**< position in array 'vars' */
1313  )
1314 {
1315  SCIP_Bool infeasible;
1316  SCIP_NODE* node1;
1317  SCIP_NODE* node2;
1318 
1319  /* check whether the variable selected for branching has a nonzero LP solution */
1320  assert(!SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[branchpos])));
1321  assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(indvars[branchpos])));
1322  assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(indvars[branchpos]), 1.0));
1323 
1324  /* create branches */
1325  SCIPdebugMsg(scip, "apply unbalanced branching on variable <%s> of constraint <%s>.\n",
1326  SCIPvarGetName(indvars[branchpos]), SCIPconsGetName(branchcons));
1327 
1328  /* create node 1 */
1329 
1330  /* calculate node selection and objective estimate for node 1 */
1331  SCIP_CALL( SCIPcreateChild(scip, &node1, SCIPcalcNodeselPriority(scip, vars[branchpos], SCIP_BRANCHDIR_DOWNWARDS, 0.0),
1332  SCIPcalcChildEstimate(scip, vars[branchpos], 0.0) ) );
1333 
1334  /* fix branching variable to zero */
1335  SCIP_CALL( fixVariableZeroNode(scip, vars[branchpos], node1, &infeasible) );
1336  assert(! infeasible);
1337 
1338  /* create node 2 */
1339 
1340  /* if the new number of nonzero variables is equal to the number of allowed nonzero variables;
1341  * i.e. cardinality constraint is saturated */
1342  assert(branchnnonzero + 1 <= cardval);
1343  if( branchnnonzero + 1 == cardval )
1344  {
1345  SCIP_Real nodeselest;
1346  SCIP_Real objest;
1347  int cnt;
1348  int j;
1349 
1350  /* calculate node selection and objective estimate for node 2 */
1351  nodeselest = 0.0;
1352  objest = 0.0;
1353  cnt = 0;
1354  for( j = 0; j < nvars; ++j )
1355  {
1356  /* we only consider variables in constraint that are not the branching variable and are not fixed to nonzero */
1357  if( j != branchpos && SCIPvarGetLbLocal(indvars[j]) != 1.0 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j]))
1358  && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j]))
1359  )
1360  {
1361  nodeselest += SCIPcalcNodeselPriority(scip, vars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1362  objest += SCIPcalcChildEstimate(scip, vars[j], 0.0);
1363  ++cnt;
1364  }
1365  }
1366  assert(cnt == nvars - (1 + branchnnonzero));
1367  assert(cnt > 0);
1368 
1369  /* take the average of the individual estimates */
1370  objest = objest / (SCIP_Real) cnt;
1371 
1372  /* create node 2 */
1373  SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) );
1374 
1375  /* indicate that branching variable may be treated as nonzero */
1376  SCIP_CALL( SCIPchgVarLbNode(scip, node2, indvars[branchpos], 1.0) );
1377 
1378  /* fix variables to zero since cardinality constraint is now saturated */
1379  for( j = 0; j < nvars; ++j )
1380  {
1381  /* we only consider variables in constraint that are not the branching variable and are not fixed to nonzero */
1382  if( j != branchpos && SCIPvarGetLbLocal(indvars[j]) != 1.0
1383  && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j]))
1384  && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j]))
1385  )
1386  {
1387  SCIP_CALL( fixVariableZeroNode(scip, vars[j], node2, &infeasible) );
1388  assert(!infeasible);
1389  }
1390  }
1391  }
1392  else
1393  {
1394  /* calculate node selection estimate for node 2 */
1395  SCIP_CALL( SCIPcreateChild(scip, &node2, 0.0, SCIPgetLocalTransEstimate(scip)) );
1396 
1397  /* indicate that branching variable may be treated as nonzero */
1398  SCIP_CALL( SCIPchgVarLbNode(scip, node2, indvars[branchpos], 1.0) );
1399  }
1400 
1401  return SCIP_OKAY;
1402 }
1403 
1404 /** apply balanced branching (see the function enforceCardinality() for further information) */
1405 static
1407  SCIP* scip, /**< SCIP pointer */
1408  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1409  SCIP_SOL* sol, /**< solution to be enforced (or NULL) */
1410  SCIP_CONS* branchcons, /**< cardinality constraint */
1411  SCIP_VAR** vars, /**< variables of constraint */
1412  SCIP_VAR** indvars, /**< indicator variables */
1413  int nvars, /**< number of variables of constraint */
1414  int cardval, /**< cardinality value of constraint */
1415  int branchnnonzero, /**< number of variables that are fixed to be nonzero */
1416  int branchpos, /**< position in array 'vars' */
1417  SCIP_Real balancedcutoff /**< cut off value for deciding whether to apply balanced branching */
1418  )
1419 {
1420  SCIP_VAR** branchvars;
1421  SCIP_VAR** branchindvars;
1422  int nbranchvars;
1423  SCIP_Real splitval1;
1424  SCIP_Real splitval2;
1425  SCIP_Real weight1;
1426  SCIP_Real weight2;
1427  SCIP_Real sum1;
1428  SCIP_Real sum2;
1429  SCIP_Real w;
1430  int newcardval;
1431  int nnonzero;
1432  int nzero;
1433  int nbuffer;
1434  int ind;
1435  int cnt;
1436  int j;
1437 
1438  /* check parameters */
1439  if( SCIPconshdlrGetSepaFreq(conshdlr) != 1 )
1440  {
1441  SCIPerrorMessage("balanced branching is only possible if separation frequency of constraint handler is 1.\n");
1442  return SCIP_PARAMETERWRONGVAL;
1443  }
1444 
1445  cnt = 0;
1446  nzero = 0;
1447  nnonzero = 0;
1448  nbranchvars = 0;
1449 
1450  weight1 = 0.0;
1451  weight2 = 0.0;
1452  sum1 = 0.0;
1453  sum2 = 0.0;
1454 
1455  /* allocate buffer arrays */
1456  nbuffer = nvars-branchnnonzero;
1457  SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, nbuffer) );
1458  SCIP_CALL( SCIPallocBufferArray(scip, &branchindvars, nbuffer) );
1459 
1460  /* compute weight */
1461  for( j = 0; j < nvars; ++j )
1462  {
1463  SCIP_VAR* var;
1464 
1465  var = vars[j];
1466 
1467  /* if(binary) indicator variable is not fixed to 1.0 */
1468  if( SCIPvarGetLbLocal(indvars[j]) != 1.0 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var))
1469  && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
1470  {
1471  /* if implied variable is not already fixed to zero */
1472  if( !SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || !SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
1473  {
1474  SCIP_Real val = REALABS(SCIPgetSolVal(scip, sol, var));
1475 
1476  weight1 += val * (SCIP_Real) (j - (nnonzero + nzero));
1477  weight2 += val;
1478  branchindvars[nbranchvars] = indvars[j];
1479  branchvars[nbranchvars++] = var;
1480 
1481  if( !SCIPisFeasZero(scip, val) )
1482  ++cnt;
1483  }
1484  else
1485  ++nzero;
1486  }
1487  else
1488  ++nnonzero;
1489  }
1490  assert(nnonzero == branchnnonzero);
1491  assert(nbranchvars <= nvars - branchnnonzero);
1492 
1493  assert(cnt >= cardval-nnonzero);
1494  assert(!SCIPisFeasZero(scip, weight2));
1495  w = weight1/weight2; /*lint !e414*/
1496 
1497  ind = (int)SCIPfloor(scip, w);
1498  assert(0 <= ind && ind < nbranchvars-1);
1499 
1500  /* compute LP sums */
1501  for( j = 0; j <= ind; ++j )
1502  {
1503  SCIP_Real val;
1504 
1505  val = SCIPgetSolVal(scip, sol, branchvars[j]);
1506 
1507  if( SCIPisFeasPositive(scip, val) )
1508  {
1509  assert(SCIPisFeasPositive(scip, SCIPvarGetUbLocal(branchvars[j])));
1510  sum1 += val / SCIPvarGetUbLocal(branchvars[j]);
1511  }
1512  else if( SCIPisFeasNegative(scip, val) )
1513  {
1514  assert(SCIPisFeasNegative(scip, SCIPvarGetLbLocal(branchvars[j])));
1515  sum1 += val / SCIPvarGetLbLocal(branchvars[j]);
1516  }
1517  }
1518  for( j = ind+1; j < nbranchvars; ++j )
1519  {
1520  SCIP_Real val;
1521 
1522  val = SCIPgetSolVal(scip, sol, branchvars[j]);
1523 
1524  if( SCIPisFeasPositive(scip, val) )
1525  {
1526  assert(SCIPisFeasPositive(scip, SCIPvarGetUbLocal(branchvars[j])));
1527  sum2 += val/SCIPvarGetUbLocal(branchvars[j]);
1528  }
1529  else if( SCIPisFeasNegative(scip, val) )
1530  {
1531  assert(SCIPisFeasNegative(scip, SCIPvarGetLbLocal(branchvars[j])));
1532  sum2 += val/SCIPvarGetLbLocal(branchvars[j]);
1533  }
1534  }
1535 
1536  /* compute cardinality values of branching constraints */
1537  newcardval = cardval - nnonzero;
1538  splitval1 = sum1 + (SCIP_Real)newcardval - sum2 - 1.0;/*lint !e834*/
1539  splitval1 = SCIPfloor(scip, splitval1/2);
1540  splitval1 = MAX(splitval1, 0);
1541  assert((int)splitval1 >= 0);
1542  assert((int)splitval1 <= MIN(newcardval-1, ind));
1543  splitval2 = (SCIP_Real)(newcardval-1);
1544  splitval2 -= splitval1;
1545 
1546  /* the lower or upper LP row of each branching constraint should cut off the current LP solution
1547  * if this is not the case, then use unbalanced branching */
1548  if ( !SCIPisFeasLT(scip, (SCIP_Real) splitval1 + balancedcutoff, sum1) ||
1549  !SCIPisFeasLT(scip, (SCIP_Real) splitval2 + balancedcutoff, sum2) )
1550  {
1551  SCIP_CALL( branchUnbalancedCardinality(scip, sol, branchcons, vars, indvars, nvars, cardval,
1552  branchnnonzero, branchpos) );
1553  }
1554  else
1555  {
1556  char name[SCIP_MAXSTRLEN];
1557  SCIP_NODE* node1;
1558  SCIP_NODE* node2;
1559  SCIP_CONS* cons1;
1560  SCIP_CONS* cons2;
1561 
1562  SCIPdebugMsg(scip, "apply balanced branching on constraint <%s>.\n", SCIPconsGetName(branchcons));
1563 
1564  if( SCIPisFeasZero(scip, splitval1) )
1565  {
1566  SCIP_Bool infeasible;
1567  SCIP_Real nodeselest;
1568  SCIP_Real objest;
1569 
1570  nodeselest = 0.0;
1571  objest = 0.0;
1572 
1573  /* calculate node selection and objective estimate for node */
1574  for( j = 0; j <= ind; ++j )
1575  {
1576  nodeselest += SCIPcalcNodeselPriority(scip, branchvars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1577  objest += SCIPcalcChildEstimate(scip, branchvars[j], 0.0);
1578  }
1579 
1580  /* take the average of the individual estimates */
1581  objest = objest/(SCIP_Real)(ind + 1.0);
1582 
1583  /* create node 1 */
1584  SCIP_CALL( SCIPcreateChild(scip, &node1, nodeselest, objest) );
1585 
1586  for( j = 0; j <= ind; ++j )
1587  {
1588  SCIP_CALL( fixVariableZeroNode(scip, branchvars[j], node1, &infeasible) );
1589  assert(!infeasible);
1590  }
1591  }
1592  else
1593  {
1594  /* calculate node selection and objective estimate for node */
1595  SCIP_CALL( SCIPcreateChild(scip, &node1, 0.0, SCIPgetLocalTransEstimate(scip)) );
1596 
1597  /* create branching constraint for node 1 */
1598  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "brleft_#%d", SCIPgetNNodes(scip));
1599  SCIP_CALL( SCIPcreateConsCardinality(scip, &cons1, name, ind+1, branchvars, (int)splitval1, branchindvars, NULL,
1600  FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, TRUE) );
1601 
1602  /* add constraint to node */
1603  SCIP_CALL( SCIPaddConsNode(scip, node1, cons1, NULL) );
1604 
1605  /* release constraint */
1606  SCIP_CALL( SCIPreleaseCons(scip, &cons1) );
1607  }
1608 
1609  if( SCIPisFeasZero(scip, splitval2) )
1610  {
1611  SCIP_Bool infeasible;
1612  SCIP_Real nodeselest;
1613  SCIP_Real objest;
1614 
1615  nodeselest = 0.0;
1616  objest = 0.0;
1617 
1618  /* calculate node selection and objective estimate for node */
1619  for( j = ind+1; j < nbranchvars; ++j )
1620  {
1621  nodeselest += SCIPcalcNodeselPriority(scip, branchvars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1622  objest += SCIPcalcChildEstimate(scip, branchvars[j], 0.0);
1623  }
1624  assert(nbranchvars - (ind + 1) > 0);
1625 
1626  /* take the average of the individual estimates */
1627  objest = objest/((SCIP_Real)(nbranchvars - (ind + 1)));/*lint !e414*/
1628 
1629  /* create node 1 */
1630  SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) );
1631 
1632  for( j = ind+1; j < nbranchvars; ++j )
1633  {
1634  SCIP_CALL( fixVariableZeroNode(scip, branchvars[j], node2, &infeasible) );
1635  assert(!infeasible);
1636  }
1637  }
1638  else
1639  {
1640  /* calculate node selection and objective estimate for node */
1641  SCIP_CALL( SCIPcreateChild(scip, &node2, 0.0, SCIPgetLocalTransEstimate(scip)) );
1642 
1643  /* shift the second half of variables */
1644  cnt = 0;
1645  for( j = ind+1; j < nbranchvars; ++j )
1646  {
1647  branchvars[cnt] = branchvars[j];
1648  branchindvars[cnt++] = branchindvars[j];
1649  }
1650  assert(cnt == nbranchvars - (ind + 1));
1651 
1652  /* create branching constraint for node 2 */
1653  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "brright_#%d", SCIPgetNNodes(scip));
1654  SCIP_CALL( SCIPcreateConsCardinality(scip, &cons2, name, cnt, branchvars, (int)splitval2, branchindvars, NULL,
1655  FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE, FALSE, TRUE) );
1656 
1657  /* add constraint to node */
1658  SCIP_CALL( SCIPaddConsNode(scip, node2, cons2, NULL) );
1659 
1660  /* release constraint */
1661  SCIP_CALL( SCIPreleaseCons(scip, &cons2) );
1662  }
1663  }
1664 
1665  /* free buffer arrays */
1666  SCIPfreeBufferArray(scip, &branchindvars);
1667  SCIPfreeBufferArray(scip, &branchvars);
1668 
1669  return SCIP_OKAY;
1670 }
1671 
1672 /** enforcement method
1673  *
1674  * We check whether the current solution is feasible. If not, the cardinality constraints can be enforced by different
1675  * branching rules:
1676  *
1677  * - Unbalanced branching: Branch on the neighborhood of a single variable \f$i\f$, i.e., in one branch \f$x_i\f$ is
1678  * fixed to zero and in the other we modify cardinality constraints \f$|\mbox{supp}(x)| \leq k\f$ with \f$i\in D\f$ to
1679  * \f$|\mbox{supp}(x_{D\setminus i}) \leq k-1\f$
1680  *
1681  * - Balanced branching: First, choose a cardinality constraint \f$|\mbox{supp}(x_D) \leq k\f$ that is violated by the
1682  * current LP solution. Then, we compute \f$W = \sum_{j=1}^n |x_i|\f$ and \f$w = \sum_{j=1}^n j\, |x_i|\f$. Next,
1683  * search for the index \f$r\f$ that satisfies
1684  * \f[
1685  * r \leq \frac{w}{W} < r+1.
1686  * \f]
1687  * Choose a number \f$s\f$ with \f$0\leq s < \min\{k, r\}\f$. The branches are then
1688  * \f[
1689  * |\mbox{supp}(x_{d_1}, \ldots, x_{d_r})| \leq s \qquad \mbox{and}\qquad
1690  * |\mbox{supp}(x_{d_{r+1}}, \ldots, x_{d_{n}})| \leq k-s-1,
1691  * \f]
1692  * where \f$d_1, \ldots, d_n\f$ are the elements of the set \f$D\f$.
1693  *
1694  * The branching constraint is chosen by the largest sum of variable values.
1695  */
1696 static
1698  SCIP* scip, /**< SCIP pointer */
1699  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1700  SCIP_SOL* sol, /**< solution to be enforced (or NULL) */
1701  int nconss, /**< number of constraints */
1702  SCIP_CONS** conss, /**< indicator constraints */
1703  SCIP_RESULT* result /**< result */
1704  )
1705 {
1706  SCIP_CONSHDLRDATA* conshdlrdata;
1707  SCIP_CONSDATA* consdata;
1708  SCIP_CONS* branchcons;
1709  SCIP_Real maxweight;
1710  SCIP_VAR** indvars;
1711  SCIP_VAR** vars;
1712  int nvars;
1713  int cardval;
1714 
1715  SCIP_Bool branchbalanced = FALSE;
1716  SCIP_Bool branchallpos = TRUE;
1717  SCIP_Bool branchallneg = TRUE;
1718  int branchnnonzero;
1719  int branchpos;
1720  int c;
1721 
1722  assert(scip != NULL);
1723  assert(conshdlr != NULL);
1724  assert(conss != NULL);
1725  assert(result != NULL);
1726 
1727  maxweight = -SCIP_REAL_MAX;
1728  branchcons = NULL;
1729  branchnnonzero = -1;
1730  branchpos = -1;
1731 
1732  SCIPdebugMsg(scip, "Enforcing cardinality constraints <%s>.\n", SCIPconshdlrGetName(conshdlr) );
1733  *result = SCIP_FEASIBLE;
1734 
1735  /* get constraint handler data */
1736  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1737  assert(conshdlrdata != NULL);
1738 
1739  /* search for a constraint with largest violation; from this constraint, we select the variable with largest LP value */
1740  for( c = 0; c < nconss; ++c )
1741  {
1742  SCIP_CONS* cons;
1743  SCIP_Bool cutoff;
1744  SCIP_Real weight;
1745  SCIP_Real maxval;
1746  SCIP_Bool allpos = TRUE;
1747  SCIP_Bool allneg = TRUE;
1748  int nnonzero; /* number of variables that are currently deactivated in constraint */
1749  int pos; /* position of variable with largest LP solution value */
1750  int nchgdomain;
1751  int cnt;
1752  int j;
1753 
1754  cons = conss[c];
1755  assert(cons != NULL);
1756  consdata = SCIPconsGetData(cons);
1757  assert(consdata != NULL);
1758 
1759  nchgdomain = 0;
1760  cnt = 0;
1761  nnonzero = 0;
1762  pos = -1;
1763  nvars = consdata->nvars;
1764  vars = consdata->vars;
1765  indvars = consdata->indvars;
1766  cardval = consdata->cardval;
1767 
1768  /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
1769  if( nvars < 2 )
1770  continue;
1771 
1772  /* first perform propagation (it might happen that standard propagation is turned off) */
1773  SCIP_CALL( propCardinality(scip, cons, consdata, &cutoff, &nchgdomain) );
1774 
1775  SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n",
1776  SCIPconsGetName(cons), cutoff, nchgdomain);
1777  if( cutoff )
1778  {
1779  *result = SCIP_CUTOFF;
1780  return SCIP_OKAY;
1781  }
1782  if( nchgdomain > 0 )
1783  {
1784  *result = SCIP_REDUCEDDOM;
1785  return SCIP_OKAY;
1786  }
1787  assert(nchgdomain == 0);
1788 
1789  /* check constraint */
1790  weight = 0.0;
1791  maxval = -SCIPinfinity(scip);
1792 
1793  for( j = 0; j < nvars; ++j )
1794  {
1795  SCIP_VAR* var;
1796 
1797  /* check whether indicator variable is zero, but variable in cardinality constraint is not fixed to zero;
1798  * if the variable is not multiaggregated this case should already be handled in propagation */
1799  if( SCIPvarGetUbLocal(indvars[j]) == 0.0 &&
1800  (
1801  !SCIPisFeasZero(scip, SCIPvarGetLbLocal(vars[j])) || !SCIPisFeasZero(scip, SCIPvarGetUbLocal(vars[j]))
1802  )
1803  )
1804  {
1805  *result = SCIP_CUTOFF;
1806  return SCIP_OKAY;
1807  }
1808 
1809  assert(SCIPvarGetStatus(indvars[j]) != SCIP_VARSTATUS_MULTAGGR);
1810 
1811  var = vars[j];
1812 
1813  /* variable is not fixed to nonzero */
1814  if( SCIPvarGetLbLocal(indvars[j]) != 1.0
1815  && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var))
1816  && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var))
1817  )
1818  {
1819  SCIP_Real val;
1820 
1821  val = SCIPgetSolVal(scip, sol, var);
1822  if( SCIPisFeasPositive(scip, val))
1823  allneg = FALSE;
1824  else if( SCIPisFeasNegative(scip, val))
1825  allpos = FALSE;
1826  val = REALABS(val);
1827 
1828  if( !SCIPisFeasZero(scip, val) )
1829  {
1830  /* determine maximum nonzero-variable solution value */
1831  if( SCIPisFeasGT(scip, val, maxval) )
1832  {
1833  pos = j;
1834  maxval = val;
1835  }
1836 
1837  weight += val;
1838  ++cnt;
1839  }
1840  }
1841  else
1842  ++nnonzero;
1843  }
1844  weight -= cardval;
1845  weight += nnonzero;
1846 
1847  /* if we detected a cut off */
1848  if( nnonzero > cardval )
1849  {
1850  SCIPdebugMsg(scip, "Detected cut off: constraint <%s> has %d many variables that can be treated as nonzero, \
1851  although only %d many are feasible.\n", SCIPconsGetName(cons), nnonzero, cardval);
1852  *result = SCIP_CUTOFF;
1853  return SCIP_OKAY;
1854  }
1855  /* else if domain can be reduced (since node 2 created in branchUnbalancedCardinality() would be infeasible) */
1856  else if( cnt > 0 && nnonzero + 1 > cardval )
1857  {
1858  SCIP_Bool infeasible;
1859  int v;
1860 
1861  for( v = 0; v < nvars; ++v )
1862  {
1863  SCIP_VAR* var;
1864 
1865  var = vars[v];
1866 
1867  /* variable is not fixed to nonzero */
1868  if( !SCIPisFeasEQ(scip, SCIPvarGetLbLocal(indvars[v]), 1.0)
1869  && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var))
1870  && !SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var))
1871  )
1872  {
1873  SCIP_CALL( fixVariableZeroNode(scip, var, SCIPgetCurrentNode(scip), &infeasible) );
1874  assert(!infeasible);
1875  SCIPdebugMsg(scip, "detected domain reduction in enforcing: fixed variable <%s> to zero.\n", SCIPvarGetName(var));
1876  }
1877  }
1878 
1879  *result = SCIP_REDUCEDDOM;
1880  return SCIP_OKAY;
1881  }
1882 
1883  /* if constraint is violated */
1884  if( cnt > cardval - nnonzero && weight > maxweight )
1885  {
1886  maxweight = weight;
1887  branchcons = cons;
1888  branchnnonzero = nnonzero;
1889  branchpos = pos;
1890  branchallneg = allneg;
1891  branchallpos = allpos;
1892  }
1893  }
1894 
1895  /* if all constraints are feasible */
1896  if( branchcons == NULL )
1897  {
1898  SCIP_SOL* primsol;
1899  SCIP_Bool success;
1900 
1901  /* polish primal solution */
1902  SCIP_CALL( SCIPcreateSolCopy(scip, &primsol, sol) );
1903  SCIP_CALL( polishPrimalSolution(scip, conss, nconss, sol, primsol) );
1904  SCIP_CALL( SCIPtrySol(scip, primsol, FALSE, TRUE, FALSE, TRUE, FALSE, &success) );
1905  SCIP_CALL( SCIPfreeSol(scip, &primsol) );
1906 
1907  SCIPdebugMsg(scip, "All cardinality constraints are feasible.\n");
1908  return SCIP_OKAY;
1909  }
1910  assert(branchnnonzero >= 0);
1911  assert(branchpos >= 0);
1912 
1913  /* get data for branching or domain reduction */
1914  consdata = SCIPconsGetData(branchcons);
1915  assert(consdata != NULL);
1916  nvars = consdata->nvars;
1917  vars = consdata->vars;
1918  indvars = consdata->indvars;
1919  cardval = consdata->cardval;
1920 
1921  /* we only use balanced branching if either the lower or the upper bound row of the branching constraint is known
1922  * to be tight or violated */
1923  if( conshdlrdata->branchbalanced && !SCIPisFeasNegative(scip, maxweight) && ( branchallneg || branchallpos )
1924  && (conshdlrdata->balanceddepth == -1 || SCIPgetDepth(scip) <= conshdlrdata->balanceddepth)
1925  )
1926  {
1927  branchbalanced = TRUE;
1928  }
1929 
1930  /* apply branching rule */
1931  if( branchbalanced )
1932  {
1933  SCIP_CALL( branchBalancedCardinality(scip, conshdlr, sol, branchcons, vars, indvars, nvars, cardval, branchnnonzero, branchpos,
1934  conshdlrdata->balancedcutoff) );
1935  }
1936  else
1937  {
1938  SCIP_CALL( branchUnbalancedCardinality(scip, sol, branchcons, vars, indvars, nvars, cardval, branchnnonzero,
1939  branchpos) );
1940  }
1941 
1942  SCIP_CALL( SCIPresetConsAge(scip, branchcons) );
1943  *result = SCIP_BRANCHED;
1944 
1945  return SCIP_OKAY;
1946 }
1947 
1948 /** Generate row
1949  *
1950  * We generate the row corresponding to the following simple valid inequalities:
1951  * \f[
1952  * \frac{x_1}{u_1} + \ldots + \frac{x_n}{u_n} \leq k\qquad\mbox{and}\qquad
1953  * \frac{x_1}{\ell_1} + \ldots + \frac{x_n}{\ell_1} \leq k,
1954  * \f]
1955  * where \f$\ell_1, \ldots, \ell_n\f$ and \f$u_1, \ldots, u_n\f$ are the nonzero and finite lower and upper bounds of
1956  * the variables \f$x_1, \ldots, x_n\f$ and k is the right hand side of the cardinality constraint. If at least k upper
1957  * bounds < 0 or a lower bounds > 0, the constraint itself is redundant, so the cut is not applied (lower bounds > 0
1958  * and upper bounds < 0 are usually detected in presolving or propagation). Infinite bounds and zero are skipped. Thus
1959  * \f$\ell_1, \ldots, \ell_n\f$ are all negative, which results in the \f$\leq\f$ inequality.
1960  *
1961  * Note that in fact, any mixture of nonzero finite lower and upper bounds would lead to a valid inequality as
1962  * above. However, usually either the lower or upper bound is nonzero. Thus, the above inequalities are the most
1963  * interesting.
1964  */
1965 static
1967  SCIP* scip, /**< SCIP pointer */
1968  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1969  SCIP_CONS* cons, /**< constraint */
1970  SCIP_Bool local, /**< produce local cut? */
1971  SCIP_ROW** rowlb, /**< output: row for lower bounds (or NULL if not needed) */
1972  SCIP_ROW** rowub /**< output: row for upper bounds (or NULL if not needed) */
1973  )
1974 {
1975  char name[SCIP_MAXSTRLEN];
1976  SCIP_CONSDATA* consdata;
1977  SCIP_VAR** vars;
1978  SCIP_Real* vals;
1979  SCIP_Real val;
1980  int nvars;
1981  int cnt;
1982  int j;
1983 
1984  assert(scip != NULL);
1985  assert(conshdlr != NULL);
1986  assert(cons != NULL);
1987 
1988  consdata = SCIPconsGetData(cons);
1989  assert(consdata != NULL);
1990  assert(consdata->vars != NULL);
1991  assert(consdata->indvars != NULL);
1992 
1993  nvars = consdata->nvars;
1994  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1995  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
1996 
1997  /* take care of upper bounds */
1998  if( rowub != NULL )
1999  {
2000  int cardval;
2001 
2002  cnt = 0;
2003  cardval = consdata->cardval;
2004  for( j = 0; j < nvars; ++j )
2005  {
2006  if( local )
2007  val = SCIPvarGetLbLocal(consdata->vars[j]);
2008  else
2009  val = SCIPvarGetUbGlobal(consdata->vars[j]);
2010 
2011  /* if a variable may be treated as nonzero, then update cardinality value */
2012  if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->indvars[j]), 1.0) )
2013  {
2014  --cardval;
2015  continue;
2016  }
2017 
2018  if( !SCIPisInfinity(scip, val) && !SCIPisZero(scip, val) && !SCIPisNegative(scip, val) )
2019  {
2020  assert(consdata->vars[j] != NULL);
2021  vars[cnt] = consdata->vars[j];
2022  vals[cnt++] = 1.0/val;
2023  }
2024  }
2025  assert(cardval >= 0);
2026 
2027  /* if cut is meaningful */
2028  if( cnt > cardval )
2029  {
2030  /* create upper bound inequality if at least two of the bounds are finite and nonzero */
2031  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cardub#%s", SCIPconsGetName(cons));
2032  SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowub, conshdlr, name, -SCIPinfinity(scip), (SCIP_Real)cardval,
2033  local, TRUE, FALSE) );
2034  SCIP_CALL( SCIPaddVarsToRow(scip, *rowub, cnt, vars, vals) );
2035  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, *rowub, NULL) ) );
2036  }
2037  }
2038 
2039  /* take care of lower bounds */
2040  if( rowlb != NULL )
2041  {
2042  int cardval;
2043 
2044  cnt = 0;
2045  cardval = consdata->cardval;
2046  for( j = 0; j < nvars; ++j )
2047  {
2048  if( local )
2049  val = SCIPvarGetLbLocal(consdata->vars[j]);
2050  else
2051  val = SCIPvarGetLbGlobal(consdata->vars[j]);
2052 
2053  /* if a variable may be treated as nonzero, then update cardinality value */
2054  if( SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->indvars[j]), 1.0) )
2055  {
2056  --cardval;
2057  continue;
2058  }
2059 
2060  if( !SCIPisInfinity(scip, -val) && !SCIPisZero(scip, val) && !SCIPisPositive(scip, val) )
2061  {
2062  assert(consdata->vars[j] != NULL);
2063  vars[cnt] = consdata->vars[j];
2064  vals[cnt++] = 1.0/val;
2065  }
2066  }
2067  assert(cardval >= 0);
2068 
2069  /* if cut is meaningful */
2070  if( cnt > cardval )
2071  {
2072  /* create lower bound inequality if at least two of the bounds are finite and nonzero */
2073  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cardlb#%s", SCIPconsGetName(cons));
2074  SCIP_CALL( SCIPcreateEmptyRowCons(scip, rowlb, conshdlr, name, -SCIPinfinity(scip), (SCIP_Real)cardval,
2075  local, TRUE, FALSE) );
2076  SCIP_CALL( SCIPaddVarsToRow(scip, *rowlb, nvars, vars, vals) );
2077  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, *rowlb, NULL) ) );
2078  }
2079  }
2080 
2081  SCIPfreeBufferArray(scip, &vals);
2082  SCIPfreeBufferArray(scip, &vars);
2083 
2084  return SCIP_OKAY;
2085 }
2086 
2087 /** initialize or separate bound inequalities from cardinality constraints
2088  * (see the function \ref generateRowCardinality() for an explanation of bound inequalities)
2089  */
2090 static
2092  SCIP* scip, /**< SCIP pointer */
2093  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2094  SCIP_CONS** conss, /**< cardinality constraints */
2095  int nconss, /**< number of cardinality constraints */
2096  SCIP_SOL* sol, /**< LP solution to be separated (or NULL) */
2097  SCIP_Bool solvedinitlp, /**< TRUE if initial LP relaxation at a node is solved */
2098  int* ngen, /**< pointer to store number of cuts generated (or NULL) */
2099  SCIP_Bool* cutoff /**< pointer to store whether a cutoff occurred */
2100  )
2101 {
2102  int cnt = 0;
2103  int c;
2104 
2105  assert(scip != NULL);
2106  assert(conss != NULL);
2107 
2108  *cutoff = FALSE;
2109 
2110  for( c = nconss-1; c >= 0; --c )
2111  {
2112  SCIP_CONSDATA* consdata;
2113  SCIP_ROW* rowub = NULL;
2114  SCIP_ROW* rowlb = NULL;
2115  SCIP_Bool release = FALSE;
2116 
2117  assert(conss != NULL);
2118  assert(conss[c] != NULL);
2119  consdata = SCIPconsGetData(conss[c]);
2120  assert(consdata != NULL);
2121 
2122  if( solvedinitlp )
2123  SCIPdebugMsg(scip, "Separating inequalities for cardinality constraint <%s>.\n", SCIPconsGetName(conss[c]) );
2124  else
2125  SCIPdebugMsg(scip, "Checking for initial rows for cardinality constraint <%s>.\n", SCIPconsGetName(conss[c]) );
2126 
2127  /* generate rows associated to cardinality constraint; the rows are stored in the constraint data
2128  * if they are globally valid */
2129  if( SCIPconsIsLocal(conss[c]) )
2130  {
2131  SCIP_CALL( generateRowCardinality(scip, conshdlr, conss[c], TRUE, &rowlb, &rowub) );
2132  release = TRUE;
2133  }
2134  else
2135  {
2136  if( consdata->rowub == NULL || consdata->rowlb == NULL )
2137  {
2138  SCIP_CALL( generateRowCardinality(scip, conshdlr, conss[c], FALSE,
2139  (consdata->rowlb == NULL) ? &consdata->rowlb : NULL,
2140  (consdata->rowub == NULL) ? &consdata->rowub : NULL) );/*lint !e826*/
2141  }
2142  rowub = consdata->rowub;
2143  rowlb = consdata->rowlb;
2144  }
2145 
2146  /* put corresponding rows into LP */
2147  if( rowub != NULL && !SCIProwIsInLP(rowub) && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, rowub) ) )
2148  {
2149  assert(SCIPisInfinity(scip, -SCIProwGetLhs(rowub)));
2150  assert(SCIPisLE(scip, SCIProwGetRhs(rowub), (SCIP_Real)consdata->cardval));
2151 
2152  SCIP_CALL( SCIPaddCut(scip, NULL, rowub, FALSE, cutoff) );
2153  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, rowub, NULL) ) );
2154 
2155  if( solvedinitlp )
2156  {
2157  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
2158  }
2159  ++cnt;
2160  }
2161 
2162  if( ! (*cutoff) && rowlb != NULL && !SCIProwIsInLP(rowlb)
2163  && ( solvedinitlp || SCIPisCutEfficacious(scip, sol, rowlb) )
2164  )
2165  {
2166  assert(SCIPisInfinity(scip, -SCIProwGetLhs(rowlb)));
2167  assert(SCIPisLE(scip, SCIProwGetRhs(rowlb), (SCIP_Real)consdata->cardval));
2168 
2169  SCIP_CALL( SCIPaddCut(scip, NULL, rowlb, FALSE, cutoff) );
2170  SCIPdebug( SCIP_CALL( SCIPprintRow(scip, rowlb, NULL) ) );
2171 
2172  if( solvedinitlp )
2173  {
2174  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
2175  }
2176  ++cnt;
2177  }
2178 
2179  if( release )
2180  {
2181  if( rowlb != NULL )
2182  {
2183  SCIP_CALL( SCIPreleaseRow(scip, &rowlb) );
2184  }
2185  if( rowub != NULL )
2186  {
2187  SCIP_CALL( SCIPreleaseRow(scip, &rowub) );
2188  }
2189  }
2190 
2191  if( *cutoff )
2192  break;
2193  }
2194 
2195  /* store number of generated cuts */
2196  if( ngen != NULL )
2197  *ngen = cnt;
2198 
2199  return SCIP_OKAY;
2200 }
2201 
2202 /** separates cardinality constraints for arbitrary solutions */
2203 static
2205  SCIP* scip, /**< SCIP pointer */
2206  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2207  SCIP_SOL* sol, /**< solution to be separated (or NULL) */
2208  int nconss, /**< number of constraints */
2209  SCIP_CONS** conss, /**< cardinality constraints */
2210  SCIP_RESULT* result /**< result */
2211  )
2212 {
2213  SCIP_Bool cutoff;
2214  int ngen = 0;
2215 
2216  assert(scip != NULL);
2217  assert(conshdlr != NULL);
2218  assert(conss != NULL);
2219  assert(result != NULL);
2220 
2221  *result = SCIP_DIDNOTRUN;
2222 
2223  if( nconss == 0 )
2224  return SCIP_OKAY;
2225 
2226  /* only separate cuts if we are not close to terminating */
2227  if( SCIPisStopped(scip) )
2228  return SCIP_OKAY;
2229 
2230  *result = SCIP_DIDNOTFIND;
2231 
2232  /* separate bound inequalities from cardinality constraints */
2233  SCIP_CALL( initsepaBoundInequalityFromCardinality(scip, conshdlr, conss, nconss, sol, TRUE, &ngen, &cutoff) );
2234  if( cutoff )
2235  {
2236  *result = SCIP_CUTOFF;
2237  return SCIP_OKAY;
2238  }
2239 
2240  /* evaluate results */
2241  if( ngen > 0 )
2242  *result = SCIP_SEPARATED;
2243  SCIPdebugMsg(scip, "Separated %d bound inequalities.\n", ngen);
2244 
2245  return SCIP_OKAY;
2246 }
2247 
2248 /* ---------------------------- constraint handler callback methods ----------------------*/
2249 
2250 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2251 static
2252 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCardinality)
2253 { /*lint --e{715}*/
2254  assert(scip != NULL);
2255  assert(conshdlr != NULL);
2256  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2257 
2258  /* call inclusion method of constraint handler */
2260 
2261  *valid = TRUE;
2262 
2263  return SCIP_OKAY;
2264 }
2265 
2266 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
2267 static
2268 SCIP_DECL_CONSFREE(consFreeCardinality)
2269 {
2270  SCIP_CONSHDLRDATA* conshdlrdata;
2272  assert(scip != NULL);
2273  assert(conshdlr != NULL);
2274  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2275 
2276  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2277  assert(conshdlrdata != NULL);
2278 
2279  /* free hash map */
2280  if( conshdlrdata->varhash != NULL )
2281  {
2282  SCIPhashmapFree(&conshdlrdata->varhash);
2283  }
2284 
2285  SCIPfreeBlockMemory(scip, &conshdlrdata);
2286 
2287  return SCIP_OKAY;
2288 }
2289 
2290 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
2291 static
2292 SCIP_DECL_CONSEXITSOL(consExitsolCardinality)
2293 { /*lint --e{715}*/
2294  SCIP_CONSHDLRDATA* conshdlrdata;
2295  int c;
2296 
2297  assert(scip != NULL);
2298  assert(conshdlr != NULL);
2299  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2300 
2301  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2302  assert(conshdlrdata != NULL);
2303 
2304  /* check each constraint */
2305  for( c = 0; c < nconss; ++c )
2306  {
2307  SCIP_CONSDATA* consdata;
2308 
2309  assert(conss != NULL);
2310  assert(conss[c] != NULL);
2311  consdata = SCIPconsGetData(conss[c]);
2312  assert(consdata != NULL);
2313 
2314  SCIPdebugMsg(scip, "Exiting cardinality constraint <%s>.\n", SCIPconsGetName(conss[c]) );
2315 
2316  /* free rows */
2317  if( consdata->rowub != NULL )
2318  {
2319  SCIP_CALL( SCIPreleaseRow(scip, &consdata->rowub) );
2320  }
2321  if( consdata->rowlb != NULL )
2322  {
2323  SCIP_CALL( SCIPreleaseRow(scip, &consdata->rowlb) );
2324  }
2325  }
2326 
2327  /* free hash map */
2328  if( conshdlrdata->varhash != NULL )
2329  {
2330  SCIPhashmapFree(&conshdlrdata->varhash);
2331  }
2332 
2333  return SCIP_OKAY;
2334 }
2335 
2336 /** frees specific constraint data */
2337 static
2338 SCIP_DECL_CONSDELETE(consDeleteCardinality)
2339 { /*lint --e{737, 647}*/
2340  assert(scip != NULL);
2341  assert(conshdlr != NULL);
2342  assert(cons != NULL);
2343  assert(consdata != NULL);
2344  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2345 
2346  SCIPdebugMsg(scip, "Deleting cardinality constraint <%s>.\n", SCIPconsGetName(cons) );
2347 
2348  /* drop events on transformed variables */
2349  if( SCIPconsIsTransformed(cons) )
2350  {
2351  SCIP_CONSHDLRDATA* conshdlrdata;
2352  int j;
2353 
2354  /* get constraint handler data */
2355  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2356  assert(conshdlrdata != NULL);
2357  assert(conshdlrdata->eventhdlr != NULL);
2358 
2359  for( j = 0; j < (*consdata)->nvars; ++j )
2360  {
2361  SCIP_CALL( dropVarEventCardinality(scip, conshdlrdata->eventhdlr, *consdata, (*consdata)->vars[j],
2362  (*consdata)->indvars[j], &(*consdata)->eventdatas[j]) );
2363  assert((*consdata)->eventdatas[j] == NULL);
2364  }
2365  }
2366 
2367  if( (*consdata)->weights != NULL )
2368  {
2369  SCIPfreeBlockMemoryArray(scip, &(*consdata)->weights, (*consdata)->maxvars);
2370  }
2371  SCIPfreeBlockMemoryArray(scip, &(*consdata)->eventdatas, (*consdata)->maxvars);
2372  SCIPfreeBlockMemoryArray(scip, &(*consdata)->eventvarscurrent, 4 * (*consdata)->maxvars);/*lint !e647*/
2373  SCIPfreeBlockMemoryArray(scip, &(*consdata)->eventdatascurrent, 4 * (*consdata)->maxvars);/*lint !e647*/
2374  SCIPfreeBlockMemoryArray(scip, &(*consdata)->indvars, (*consdata)->maxvars);
2375  SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->maxvars);
2376 
2377  /* free rows */
2378  if( (*consdata)->rowub != NULL )
2379  {
2380  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->rowub) );
2381  }
2382  if( (*consdata)->rowlb != NULL )
2383  {
2384  SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->rowlb) );
2385  }
2386  assert((*consdata)->rowub == NULL);
2387  assert((*consdata)->rowlb == NULL);
2388 
2389  SCIPfreeBlockMemory(scip, consdata);
2390 
2391  return SCIP_OKAY;
2392 }
2393 
2394 /** transforms constraint data into data belonging to the transformed problem */
2395 static
2396 SCIP_DECL_CONSTRANS(consTransCardinality)
2397 {
2398  SCIP_CONSDATA* consdata;
2399  SCIP_CONSHDLRDATA* conshdlrdata;
2400  SCIP_CONSDATA* sourcedata;
2401  char s[SCIP_MAXSTRLEN];
2402  int j;
2403 
2404  assert(scip != NULL);
2405  assert(conshdlr != NULL);
2406  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2407  assert(sourcecons != NULL);
2408  assert(targetcons != NULL);
2409 
2410  /* get constraint handler data */
2411  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2412  assert(conshdlrdata != NULL);
2413  assert(conshdlrdata->eventhdlr != NULL);
2414 
2415  SCIPdebugMsg(scip, "Transforming cardinality constraint: <%s>.\n", SCIPconsGetName(sourcecons) );
2416 
2417  /* get data of original constraint */
2418  sourcedata = SCIPconsGetData(sourcecons);
2419  assert(sourcedata != NULL);
2420  assert(sourcedata->nvars > 0);
2421  assert(sourcedata->nvars <= sourcedata->maxvars);
2422 
2423  /* create constraint data */
2424  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
2425 
2426  consdata->cons = NULL;
2427  consdata->nvars = sourcedata->nvars;
2428  consdata->maxvars = sourcedata->nvars;
2429  consdata->cardval = sourcedata->cardval;
2430  consdata->rowub = NULL;
2431  consdata->rowlb = NULL;
2432  consdata->eventdatascurrent = NULL;
2433  consdata->neventdatascurrent = 0;
2434  consdata->ntreatnonzeros = 0;
2435  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, consdata->nvars) );
2436  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->indvars, consdata->nvars) );
2437  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatas, consdata->nvars) );
2438  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*consdata->nvars) );/*lint !e647*/
2439  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*consdata->nvars) );/*lint !e647*/
2440 
2441  /* if weights were used */
2442  if( sourcedata->weights != NULL )
2443  {
2444  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, sourcedata->weights, consdata->nvars) );
2445  }
2446  else
2447  consdata->weights = NULL;
2448 
2449  for( j = 0; j < sourcedata->nvars; ++j )
2450  {
2451  assert(sourcedata->vars[j] != 0);
2452  assert(sourcedata->indvars[j] != 0);
2453  SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->vars[j], &(consdata->vars[j])) );
2454  SCIP_CALL( SCIPgetTransformedVar(scip, sourcedata->indvars[j], &(consdata->indvars[j])) );
2455 
2456  /* if variable is fixed to be nonzero */
2457  if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->indvars[j]), 1.0) )
2458  ++(consdata->ntreatnonzeros);
2459  }
2460 
2461  /* create transformed constraint with the same flags */
2462  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons));
2463  SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
2464  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
2465  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
2466  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
2467  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
2468  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2469 
2470  consdata->cons = *targetcons;
2471  assert(consdata->cons != NULL);
2472 
2473  /* catch bound change events on variable */
2474  for( j = 0; j < consdata->nvars; ++j )
2475  {
2476  SCIP_CALL( catchVarEventCardinality(scip, conshdlrdata->eventhdlr, consdata,
2477  consdata->vars[j], consdata->indvars[j], j, &consdata->eventdatas[j]) );
2478  assert(consdata->eventdatas[j] != NULL);
2479  }
2480 
2481 #ifdef SCIP_DEBUG
2482  if( SCIPisGT(scip, (SCIP_Real)consdata->ntreatnonzeros, consdata->cardval) )
2483  {
2484  SCIPdebugMsg(scip, "constraint <%s> has %d variables fixed to be nonzero, allthough the constraint allows \
2485  only %d nonzero variables\n", SCIPconsGetName(*targetcons), consdata->ntreatnonzeros, consdata->cardval);
2486  }
2487 #endif
2488 
2489  return SCIP_OKAY;
2490 }
2491 
2492 /** presolving method of constraint handler */
2493 static
2494 SCIP_DECL_CONSPRESOL(consPresolCardinality)
2495 { /*lint --e{715}*/
2496  int oldnfixedvars;
2497  int oldndelconss;
2498  int oldnupgdconss;
2499  int nremovedvars;
2500  SCIP_EVENTHDLR* eventhdlr;
2501  int c;
2502 
2503  assert(scip != NULL);
2504  assert(conshdlr != NULL);
2505  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2506  assert(result != NULL);
2507 
2508  SCIPdebugMsg(scip, "Presolving cardinality constraints.\n");
2509 
2510  *result = SCIP_DIDNOTRUN;
2511  SCIPdebug( oldnfixedvars = *nfixedvars; )
2512  SCIPdebug( oldndelconss = *ndelconss; )
2513  SCIPdebug( oldnupgdconss = *nupgdconss; )
2514  nremovedvars = 0;
2515 
2516  /* only run if success if possible */
2517  if( nrounds == 0 || nnewfixedvars > 0 || nnewaggrvars > 0 )
2518  {
2519  /* get constraint handler data */
2520  assert(SCIPconshdlrGetData(conshdlr) != NULL);
2521  eventhdlr = SCIPconshdlrGetData(conshdlr)->eventhdlr;
2522  assert(eventhdlr != NULL);
2523 
2524  *result = SCIP_DIDNOTFIND;
2525 
2526  /* check each constraint */
2527  for( c = 0; c < nconss; ++c )
2528  {
2529  SCIP_CONSDATA* consdata;
2530  SCIP_CONS* cons;
2531  SCIP_Bool cutoff;
2532  SCIP_Bool success;
2533 
2534  assert(conss != NULL);
2535  assert(conss[c] != NULL);
2536  cons = conss[c];
2537  consdata = SCIPconsGetData(cons);
2538 
2539  assert(consdata != NULL);
2540  assert(consdata->nvars >= 0);
2541  assert(consdata->nvars <= consdata->maxvars);
2542  assert(!SCIPconsIsModifiable(cons));
2543 
2544  /* perform one presolving round */
2545  SCIP_CALL( presolRoundCardinality(scip, cons, consdata, eventhdlr, &cutoff, &success,
2546  ndelconss, nupgdconss, nfixedvars, &nremovedvars) );
2547 
2548  if( cutoff )
2549  {
2550  SCIPdebugMsg(scip, "presolving detected cutoff.\n");
2551  *result = SCIP_CUTOFF;
2552  return SCIP_OKAY;
2553  }
2554 
2555  if( success )
2556  *result = SCIP_SUCCESS;
2557  }
2558  }
2559  (*nchgcoefs) += nremovedvars;
2560 
2561  SCIPdebugMsg(scip, "presolving fixed %d variables, removed %d variables, deleted %d constraints, \
2562  and upgraded %d constraints.\n", *nfixedvars - oldnfixedvars, nremovedvars, *ndelconss - oldndelconss,
2563  *nupgdconss - oldnupgdconss);
2564 
2565  return SCIP_OKAY;
2566 }
2567 
2568 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
2569 static
2570 SCIP_DECL_CONSINITLP(consInitlpCardinality)
2571 { /*lint --e{715}*/
2572  SCIP_Bool cutoff;
2574  assert(scip != NULL);
2575  assert(conshdlr != NULL);
2576 
2577  /* checking for initial rows for cardinality constraints */
2578  SCIP_CALL( initsepaBoundInequalityFromCardinality(scip, conshdlr, conss, nconss, NULL, FALSE, NULL, &cutoff) );
2579  assert(!cutoff);
2580 
2581  return SCIP_OKAY;
2582 }
2583 
2584 /** separation method of constraint handler for LP solutions */
2585 static
2586 SCIP_DECL_CONSSEPALP(consSepalpCardinality)
2587 { /*lint --e{715}*/
2588  assert(scip != NULL);
2589  assert(conshdlr != NULL);
2590  assert(conss != NULL);
2591  assert(result != NULL);
2592 
2593  SCIP_CALL( separateCardinality(scip, conshdlr, NULL, nconss, conss, result) );
2594 
2595  return SCIP_OKAY;
2596 }
2597 
2598 /** separation method of constraint handler for arbitrary primal solutions */
2599 static
2600 SCIP_DECL_CONSSEPASOL(consSepasolCardinality)
2601 { /*lint --e{715}*/
2602  assert(scip != NULL);
2603  assert(conshdlr != NULL);
2604  assert(conss != NULL);
2605  assert(result != NULL);
2606 
2607  SCIP_CALL( separateCardinality(scip, conshdlr, sol, nconss, conss, result) );
2608 
2609  return SCIP_OKAY;
2610 }
2611 
2612 /** constraint enforcing method of constraint handler for LP solutions */
2613 static
2614 SCIP_DECL_CONSENFOLP(consEnfolpCardinality)
2615 { /*lint --e{715}*/
2616  assert(scip != NULL);
2617  assert(conshdlr != NULL);
2618  assert(conss != NULL);
2619  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2620  assert(result != NULL);
2621 
2622  SCIP_CALL( enforceCardinality(scip, conshdlr, NULL, nconss, conss, result) );
2623 
2624  return SCIP_OKAY;
2625 }
2626 
2627 /** constraint enforcing method of constraint handler for relaxation solutions */
2628 static
2629 SCIP_DECL_CONSENFORELAX(consEnforelaxCardinality)
2630 { /*lint --e{715}*/
2631  assert( scip != NULL );
2632  assert( conshdlr != NULL );
2633  assert( conss != NULL );
2634  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2635  assert( result != NULL );
2636 
2637  SCIP_CALL( enforceCardinality(scip, conshdlr, sol, nconss, conss, result) );
2638 
2639  return SCIP_OKAY;
2640 }
2641 
2642 /** constraint enforcing method of constraint handler for pseudo solutions */
2643 static
2644 SCIP_DECL_CONSENFOPS(consEnfopsCardinality)
2645 { /*lint --e{715}*/
2646  assert(scip != NULL);
2647  assert(conshdlr != NULL);
2648  assert(conss != NULL);
2649  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2650  assert(result != NULL);
2651 
2652  SCIP_CALL( enforceCardinality(scip, conshdlr, NULL, nconss, conss, result) );
2653 
2654  return SCIP_OKAY;
2655 }
2656 
2657 /** feasibility check method of constraint handler for integral solutions
2658  *
2659  * We simply check whether more variables than allowed are nonzero in the given solution.
2660  */
2661 static
2662 SCIP_DECL_CONSCHECK(consCheckCardinality)
2663 { /*lint --e{715}*/
2664  int c;
2666  assert(scip != NULL);
2667  assert(conshdlr != NULL);
2668  assert(conss != NULL);
2669  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2670  assert(result != NULL);
2671 
2672  /* check each constraint */
2673  for( c = 0; c < nconss; ++c )
2674  {
2675  SCIP_CONSDATA* consdata;
2676  int cardval;
2677  int j;
2678  int cnt;
2679 
2680  cnt = 0;
2681  assert(conss[c] != NULL);
2682  consdata = SCIPconsGetData(conss[c]);
2683  assert(consdata != NULL);
2684  cardval = consdata->cardval;
2685  SCIPdebugMsg(scip, "Checking cardinality constraint <%s>.\n", SCIPconsGetName(conss[c]));
2686 
2687  /* check all variables */
2688  for( j = 0; j < consdata->nvars; ++j )
2689  {
2690  /* if variable is nonzero */
2691  if( !SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->vars[j])) )
2692  {
2693  ++cnt;
2694 
2695  /* if more variables than allowed are nonzero */
2696  if( cnt > cardval )
2697  {
2698  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
2699  *result = SCIP_INFEASIBLE;
2700 
2701  if( printreason )
2702  {
2703  int l;
2704 
2705  SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) );
2706  SCIPinfoMessage(scip, NULL, ";\nviolation: ");
2707 
2708  for( l = 0; l < consdata->nvars; ++l )
2709  {
2710  /* if variable is nonzero */
2711  if( !SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->vars[l])) )
2712  {
2713  SCIPinfoMessage(scip, NULL, "<%s> = %.15g ",
2714  SCIPvarGetName(consdata->vars[l]), SCIPgetSolVal(scip, sol, consdata->vars[l]));
2715  }
2716  }
2717  SCIPinfoMessage(scip, NULL, "\n");
2718  }
2719  return SCIP_OKAY;
2720  }
2721  }
2722  }
2723  }
2724  *result = SCIP_FEASIBLE;
2725 
2726  return SCIP_OKAY;
2727 }
2728 
2729 /** domain propagation method of constraint handler */
2730 static
2731 SCIP_DECL_CONSPROP(consPropCardinality)
2732 { /*lint --e{715}*/
2733  int nchgdomain = 0;
2734  int c;
2735 
2736  assert(scip != NULL);
2737  assert(conshdlr != NULL);
2738  assert(conss != NULL);
2739  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2740  assert(result != NULL);
2741  *result = SCIP_DIDNOTRUN;
2742 
2743  assert(SCIPisTransformed(scip));
2744 
2745  /* check each constraint */
2746  for( c = 0; c < nconss; ++c )
2747  {
2748  SCIP_CONS* cons;
2749  SCIP_CONSDATA* consdata;
2750  SCIP_Bool cutoff;
2751 
2752  *result = SCIP_DIDNOTFIND;
2753  assert(conss[c] != NULL);
2754  cons = conss[c];
2755  consdata = SCIPconsGetData(cons);
2756  assert(consdata != NULL);
2757  SCIPdebugMsg(scip, "Propagating cardinality constraint <%s>.\n", SCIPconsGetName(cons) );
2758 
2759  *result = SCIP_DIDNOTFIND;
2760  SCIP_CALL( propCardinality(scip, cons, consdata, &cutoff, &nchgdomain) );
2761  if( cutoff )
2762  {
2763  *result = SCIP_CUTOFF;
2764  return SCIP_OKAY;
2765  }
2766  }
2767  SCIPdebugMsg(scip, "Propagated %d domains.\n", nchgdomain);
2768  if( nchgdomain > 0 )
2769  *result = SCIP_REDUCEDDOM;
2770 
2771  return SCIP_OKAY;
2772 }
2773 
2774 /** variable rounding lock method of constraint handler
2775  *
2776  * Let lb and ub be the lower and upper bounds of a
2777  * variable. Preprocessing usually makes sure that lb <= 0 <= ub.
2778  *
2779  * - If lb < 0 then rounding down may violate the constraint.
2780  * - If ub > 0 then rounding up may violated the constraint.
2781  * - If lb > 0 or ub < 0 then the rhs of the constraint can be updated and the variable
2782  * can be removed from the constraint. Thus, we do not have to deal with it here.
2783  * - If lb == 0 then rounding down does not violate the constraint.
2784  * - If ub == 0 then rounding up does not violate the constraint.
2785  */
2786 static
2787 SCIP_DECL_CONSLOCK(consLockCardinality)
2788 {
2789  SCIP_CONSDATA* consdata;
2790  SCIP_VAR** vars;
2791  int nvars;
2792  SCIP_VAR** indvars;
2793  int j;
2794 
2795  assert(scip != NULL);
2796  assert(conshdlr != NULL);
2797  assert(cons != NULL);
2798  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2799  consdata = SCIPconsGetData(cons);
2800  assert(consdata != NULL);
2801 
2802  SCIPdebugMsg(scip, "Locking constraint <%s>.\n", SCIPconsGetName(cons));
2803 
2804  vars = consdata->vars;
2805  indvars = consdata->indvars;
2806  nvars = consdata->nvars;
2807  assert(vars != NULL);
2808 
2809  for( j = 0; j < nvars; ++j )
2810  {
2811  SCIP_VAR* var;
2812  SCIP_VAR* indvar;
2813  var = vars[j];
2814  indvar = indvars[j];
2815 
2816  /* if lower bound is negative, rounding down may violate constraint */
2817  if( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)) )
2818  {
2819  SCIP_CALL( SCIPaddVarLocks(scip, var, nlockspos, nlocksneg) );
2820  }
2821 
2822  /* additionally: if upper bound is positive, rounding up may violate constraint */
2823  if( SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var)) )
2824  {
2825  SCIP_CALL( SCIPaddVarLocks(scip, var, nlocksneg, nlockspos) );
2826  }
2827 
2828  /* add lock on indicator variable; @todo write constraint handler to handle down locks */
2829  SCIP_CALL( SCIPaddVarLocks(scip, indvar, nlockspos, nlockspos) );
2830  }
2831 
2832  return SCIP_OKAY;
2833 }
2834 
2835 /** constraint display method of constraint handler */
2836 static
2837 SCIP_DECL_CONSPRINT(consPrintCardinality)
2838 { /*lint --e{715}*/
2839  SCIP_CONSDATA* consdata;
2840  int j;
2841 
2842  assert(scip != NULL);
2843  assert(conshdlr != NULL);
2844  assert(cons != NULL);
2845  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2846 
2847  consdata = SCIPconsGetData(cons);
2848  assert(consdata != NULL);
2849 
2850  SCIPinfoMessage(scip, file, "card( ");
2851  for( j = 0; j < consdata->nvars; ++j )
2852  {
2853  if( j > 0 )
2854  SCIPinfoMessage(scip, file, ", ");
2855  SCIP_CALL( SCIPwriteVarName(scip, file, consdata->vars[j], FALSE) );
2856  if( consdata->weights == NULL )
2857  SCIPinfoMessage(scip, file, " (%d)", j+1);
2858  else
2859  SCIPinfoMessage(scip, file, " (%3.2f)", consdata->weights[j]);
2860  }
2861  SCIPinfoMessage(scip, file, ") <= %d", consdata->cardval);
2862 
2863  return SCIP_OKAY;
2864 }
2865 
2866 /** constraint copying method of constraint handler */
2867 static
2868 SCIP_DECL_CONSCOPY(consCopyCardinality)
2869 { /*lint --e{715}*/
2870  SCIP_CONSDATA* sourceconsdata;
2871  SCIP_VAR** sourcevars;
2872  SCIP_VAR** targetvars;
2873  SCIP_VAR** sourceindvars;
2874  SCIP_VAR** targetindvars;
2875  SCIP_Real* sourceweights;
2876  SCIP_Real* targetweights;
2877  const char* consname;
2878  int nvars;
2879  int v;
2880 
2881  assert(scip != NULL);
2882  assert(sourcescip != NULL);
2883  assert(sourcecons != NULL);
2884  assert(SCIPisTransformed(sourcescip));
2885  assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) == 0);
2886 
2887  *valid = TRUE;
2888 
2889  if( name != NULL )
2890  consname = name;
2891  else
2892  consname = SCIPconsGetName(sourcecons);
2893 
2894  SCIPdebugMsg(scip, "Copying cardinality constraint <%s> ...\n", consname);
2895 
2896  sourceconsdata = SCIPconsGetData(sourcecons);
2897  assert(sourceconsdata != NULL);
2898 
2899  /* get variables and weights of the source constraint */
2900  nvars = sourceconsdata->nvars;
2901 
2902  if( nvars == 0 )
2903  return SCIP_OKAY;
2904 
2905  sourcevars = sourceconsdata->vars;
2906  assert(sourcevars != NULL);
2907  sourceindvars = sourceconsdata->indvars;
2908  assert(sourceindvars != NULL);
2909  sourceweights = sourceconsdata->weights;
2910  assert(sourceweights != NULL);
2911 
2912  /* duplicate variable array */
2913  SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetvars, nvars) );
2914  SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetindvars, nvars) );
2915  SCIP_CALL( SCIPduplicateBufferArray(sourcescip, &targetweights, sourceweights, nvars) );
2916 
2917  /* get copied variables in target SCIP */
2918  for( v = 0; v < nvars && *valid; ++v )
2919  {
2920  assert(sourcevars[v] != NULL);
2921  assert(sourceindvars[v] != NULL);
2922 
2923  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &(targetvars[v]), varmap, consmap, global, valid) );
2924  if( *valid )
2925  {
2926  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceindvars[v], &(targetindvars[v]), varmap, consmap, global, valid) );
2927  }
2928  }
2929 
2930  /* only create the target constraint, if all variables could be copied */
2931  if( *valid )
2932  {
2933  SCIP_CALL( SCIPcreateConsCardinality(scip, cons, consname, nvars, targetvars, sourceconsdata->cardval, targetindvars,
2934  targetweights, initial, separate, enforce, check, propagate, local, dynamic, removable, stickingatnode) );
2935  }
2936 
2937  /* free buffer array */
2938  SCIPfreeBufferArray(sourcescip, &targetweights);
2939  SCIPfreeBufferArray(sourcescip, &targetindvars);
2940  SCIPfreeBufferArray(sourcescip, &targetvars);
2941 
2942  return SCIP_OKAY;
2943 }
2944 
2945 /** constraint method of constraint handler which returns the variables (if possible) */
2946 static
2947 SCIP_DECL_CONSGETVARS(consGetVarsCardinality)
2948 { /*lint --e{715}*/
2949  SCIP_CONSDATA* consdata;
2951  consdata = SCIPconsGetData(cons);
2952  assert(consdata != NULL);
2953 
2954  if( varssize < consdata->nvars )
2955  (*success) = FALSE;
2956  else
2957  {
2958  assert(vars != NULL);
2959 
2960  BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
2961  (*success) = TRUE;
2962  }
2963 
2964  return SCIP_OKAY;
2965 }
2966 
2967 /** constraint method of constraint handler which returns the number of variables (if possible) */
2968 static
2969 SCIP_DECL_CONSGETNVARS(consGetNVarsCardinality)
2970 { /*lint --e{715}*/
2971  SCIP_CONSDATA* consdata;
2973  consdata = SCIPconsGetData(cons);
2974  assert(consdata != NULL);
2975 
2976  (*nvars) = consdata->nvars;
2977  (*success) = TRUE;
2978 
2979  return SCIP_OKAY;
2980 }
2981 
2982 /* ---------------- Callback methods of event handler ---------------- */
2983 
2984 /* exec the event handler
2985  *
2986  * update the number of variables fixed to be nonzero
2987  * update the bound constraints
2988  */
2989 static
2990 SCIP_DECL_EVENTEXEC(eventExecCardinality)
2991 {
2992  SCIP_EVENTTYPE eventtype;
2993  SCIP_CONSDATA* consdata;
2994  SCIP_Real oldbound;
2995  SCIP_Real newbound;
2996  SCIP_VAR* var;
2997 
2998  assert(eventhdlr != NULL);
2999  assert(eventdata != NULL);
3000  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3001  assert(event != NULL);
3002 
3003  consdata = eventdata->consdata;
3004  assert(consdata != NULL);
3005  assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3006  assert(consdata->eventdatascurrent != NULL);
3007  assert(consdata->eventvarscurrent != NULL);
3008 
3009  var = SCIPeventGetVar(event);
3010  assert(var != NULL);
3011  oldbound = SCIPeventGetOldbound(event);
3012  newbound = SCIPeventGetNewbound(event);
3013  eventtype = SCIPeventGetType(event);
3014 
3015 #ifdef SCIP_DEBUG
3016  if( ( eventdata->varmarked && var == eventdata->var) || ( eventdata->indvarmarked && var == eventdata->indvar) )
3017  {
3018  int i;
3019 
3020  for( i = 0; i < consdata->neventdatascurrent; ++i )
3021  {
3022  if( var == consdata->eventvarscurrent[i] )
3023  {
3024  break;
3025  }
3026  }
3027  assert(i < consdata->neventdatascurrent);
3028  }
3029 #endif
3030 
3031  /* if variable is an indicator variable */
3032  if( var == eventdata->indvar )
3033  {
3034  assert(SCIPvarIsBinary(var));
3035  assert(consdata->cons != NULL);
3036 
3037  if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED || eventtype == SCIP_EVENTTYPE_LBRELAXED )
3038  {
3039  if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED )
3040  ++(consdata->ntreatnonzeros);
3041  else if( eventtype == SCIP_EVENTTYPE_LBRELAXED )
3042  --(consdata->ntreatnonzeros);
3043 
3044  assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3045  }
3046  else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED && ! eventdata->indvarmarked )
3047  {
3048  assert(oldbound == 1.0 && newbound == 0.0 );
3049 
3050  /* save event data for propagation */
3051  consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3052  consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3053  ++consdata->neventdatascurrent;
3054  eventdata->indvarmarked = TRUE;
3055  assert(consdata->neventdatascurrent <= 4 * consdata->maxvars);
3056  assert(var == eventdata->indvar );
3057  }
3058  }
3059 
3060  /* if variable is an implied variable,
3061  * notice that the case consdata->var = consdata->indvar is possible */
3062  if( var == eventdata->var && ! eventdata->varmarked )
3063  {
3064  if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED )
3065  {
3066  /* if variable is now fixed to be nonzero */
3067  if( !SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
3068  {
3069  /* save event data for propagation */
3070  consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3071  consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3072  ++consdata->neventdatascurrent;
3073  eventdata->varmarked = TRUE;
3074  assert(consdata->neventdatascurrent <= 4 * consdata->maxvars );
3075  assert(var == eventdata->var );
3076  }
3077  }
3078  else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED )
3079  {
3080  /* if variable is now fixed to be nonzero */
3081  if( !SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
3082  {
3083  /* save event data for propagation */
3084  consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3085  consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3086  ++consdata->neventdatascurrent;
3087  eventdata->varmarked = TRUE;
3088  assert(consdata->neventdatascurrent <= 4 * consdata->maxvars );
3089  assert(var == eventdata->var);
3090  }
3091  }
3092  }
3093  assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3094 
3095  SCIPdebugMsg(scip, "event exec cons <%s>: changed bound of variable <%s> from %f to %f (ntreatnonzeros: %d).\n",
3096  SCIPconsGetName(consdata->cons), SCIPvarGetName(SCIPeventGetVar(event)),
3097  oldbound, newbound, consdata->ntreatnonzeros);
3098 
3099  return SCIP_OKAY;
3100 }
3101 
3102 /* ---------------- Constraint specific interface methods ---------------- */
3103 
3104 /** creates the handler for cardinality constraints and includes it in SCIP */
3106  SCIP* scip /**< SCIP data structure */
3107  )
3109  SCIP_CONSHDLRDATA* conshdlrdata;
3110  SCIP_CONSHDLR* conshdlr;
3111 
3112  /* create constraint handler data */
3113  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3114  conshdlrdata->eventhdlr = NULL;
3115  conshdlrdata->varhash = NULL;
3116 
3117  /* create event handler for bound change events */
3118  SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3119  eventExecCardinality, NULL) );
3120  if( conshdlrdata->eventhdlr == NULL )
3121  {
3122  SCIPerrorMessage("event handler for cardinality constraints not found.\n");
3123  return SCIP_PLUGINNOTFOUND;
3124  }
3125 
3126  /* include constraint handler */
3129  consEnfolpCardinality, consEnfopsCardinality, consCheckCardinality, consLockCardinality, conshdlrdata) );
3130  assert(conshdlr != NULL);
3131 
3132  /* set non-fundamental callbacks via specific setter functions */
3133  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyCardinality, consCopyCardinality) );
3134  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteCardinality) );
3135  SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolCardinality) );
3136  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeCardinality) );
3137  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsCardinality) );
3138  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsCardinality) );
3139  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpCardinality) );
3140  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolCardinality, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3141  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintCardinality) );
3142  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropCardinality, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3144  /*SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropCardinality) ); @todo: implement repropagation */
3145  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCardinality, consSepasolCardinality, CONSHDLR_SEPAFREQ,
3147  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransCardinality) );
3148  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxCardinality) );
3149 
3150  /* add cardinality constraint handler parameters */
3151  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/"CONSHDLR_NAME"/branchbalanced",
3152  "whether to use balanced instead of unbalanced branching",
3153  &conshdlrdata->branchbalanced, TRUE, DEFAULT_BRANCHBALANCED, NULL, NULL) );
3154 
3155  SCIP_CALL( SCIPaddIntParam(scip, "constraints/"CONSHDLR_NAME"/balanceddepth",
3156  "maximum depth for using balanced branching (-1: no limit)",
3157  &conshdlrdata->balanceddepth, TRUE, DEFAULT_BALANCEDDEPTH, -1, INT_MAX, NULL, NULL) );
3158 
3159  SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/balancedcutoff",
3160  "determines that balanced branching is only used if the branching cut off value \
3161  w.r.t. the current LP solution is greater than a given value",
3162  &conshdlrdata->balancedcutoff, TRUE, DEFAULT_BALANCEDCUTOFF, 0.01, SCIP_REAL_MAX, NULL, NULL) );
3163 
3164  return SCIP_OKAY;
3165 }
3166 
3167 /** creates and captures a cardinality constraint
3168  *
3169  * We set the constraint to not be modifable. If the weights are non
3170  * NULL, the variables are ordered according to these weights (in
3171  * ascending order).
3172  *
3173  * @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons()
3174  */
3176  SCIP* scip, /**< SCIP data structure */
3177  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3178  const char* name, /**< name of constraint */
3179  int nvars, /**< number of variables in the constraint */
3180  SCIP_VAR** vars, /**< array with variables of constraint entries */
3181  int cardval, /**< number of variables allowed to be nonzero */
3182  SCIP_VAR** indvars, /**< indicator variables indicating which variables may be treated as nonzero
3183  * in cardinality constraint, or NULL if new indicator variables should be
3184  * introduced automatically */
3185  SCIP_Real* weights, /**< weights determining the variable order, or NULL if variables should be
3186  ordered in the same way they were added to the constraint */
3187  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3188  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3189  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3190  * Usually set to TRUE. */
3191  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3192  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3193  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3194  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3195  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3196  * Usually set to TRUE. */
3197  SCIP_Bool local, /**< is constraint only valid locally?
3198  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3199  SCIP_Bool dynamic, /**< is constraint subject to aging?
3200  * Usually set to FALSE. Set to TRUE for own cuts which
3201  * are separated as constraints. */
3202  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3203  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3204  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3205  * if it may be moved to a more global node?
3206  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3207  )
3208 {
3209  SCIP_CONSHDLRDATA* conshdlrdata;
3210  SCIP_CONSHDLR* conshdlr;
3211  SCIP_CONSDATA* consdata;
3212  SCIP_Bool modifiable;
3213  SCIP_Bool transformed;
3214  int v;
3215 
3216  modifiable = FALSE;
3217 
3218  /* find the cardinality constraint handler */
3219  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3220  if( conshdlr == NULL )
3221  {
3222  SCIPerrorMessage("<%s> constraint handler not found\n", CONSHDLR_NAME);
3223  return SCIP_PLUGINNOTFOUND;
3224  }
3225 
3226  /* get constraint handler data */
3227  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3228  assert(conshdlrdata != NULL);
3229 
3230  /* are we in the transformed problem? */
3231  transformed = SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED;
3232 
3233  /* create constraint data */
3234  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
3235  consdata->cons = NULL;
3236  consdata->vars = NULL;
3237  consdata->indvars = NULL;
3238  consdata->eventdatas = NULL;
3239  consdata->nvars = nvars;
3240  consdata->cardval = cardval;
3241  consdata->maxvars = nvars;
3242  consdata->rowub = NULL;
3243  consdata->rowlb = NULL;
3244  consdata->eventdatascurrent = NULL;
3245  consdata->eventvarscurrent = NULL;
3246  consdata->neventdatascurrent = 0;
3247  consdata->ntreatnonzeros = transformed ? 0 : -1;
3248  consdata->weights = NULL;
3249 
3250  if( nvars > 0 )
3251  {
3252  /* duplicate memory for implied variables */
3253  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->vars, vars, nvars) );
3254 
3255  /* create indicator variables if not present */
3256  if( indvars != NULL )
3257  {
3258  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->indvars, indvars, nvars) );
3259  }
3260  else
3261  {
3262  if( conshdlrdata->varhash == NULL )
3263  {
3264  /* set up hash map */
3265  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) );
3266  }
3267 
3268  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->indvars, nvars) );
3269  for( v = 0; v < nvars; ++v )
3270  {
3271  SCIP_VAR* implvar;
3272 
3273  implvar = vars[v];
3274  assert(implvar != NULL);
3275 
3276  /* check whether an indicator variable already exists for implied variable */
3277  if( SCIPhashmapExists(conshdlrdata->varhash, implvar) )
3278  {
3279  assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar) != NULL);
3280  consdata->indvars[v] = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar);
3281  }
3282  else
3283  {
3284  /* if implied variable is binary, then it is not necessary to create an indicator variable */
3285  if( SCIPvarIsBinary(implvar) )
3286  consdata->indvars[v] = implvar;
3287  else
3288  {
3289  char varname[SCIP_MAXSTRLEN];
3290  SCIP_VAR* var;
3291 
3292  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(vars[v]));
3293  SCIP_CALL( SCIPcreateVar(scip, &var, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE,
3294  NULL, NULL, NULL, NULL, NULL) );
3295  SCIP_CALL( SCIPaddVar(scip, var) );
3296  consdata->indvars[v] = var;
3297  SCIP_CALL( SCIPreleaseVar(scip, &var) );
3298  }
3299 
3300  /* insert implied variable to hash map */
3301  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, implvar, (void*) consdata->indvars[v]) );/*lint !e571*/
3302  assert(consdata->indvars[v] == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar));
3303  assert(SCIPhashmapExists(conshdlrdata->varhash, implvar));
3304  }
3305  }
3306  }
3307 
3308  /* allocate block memory */
3309  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*nvars) );/*lint !e647*/
3310  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*nvars) );/*lint !e647*/
3311  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatas, nvars) );
3312 
3313  /* check weights */
3314  if( weights != NULL )
3315  {
3316  int* dummy;
3317 
3318  /* store weights */
3319  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, weights, nvars) );
3320 
3321  /* create dummy array to make code compatible with SCIP 3.2.0
3322  * (the function SCIPsortRealPtrPtr() is not available) */
3323  SCIP_CALL( SCIPallocBufferArray(scip, &dummy, nvars) );
3324  for( v = 0; v < nvars; ++v )
3325  dummy[v] = 0;
3326 
3327  /* sort variables - ascending order */
3328  SCIPsortRealPtrPtrInt(consdata->weights, (void**)consdata->vars, (void**)consdata->indvars, dummy, nvars);
3329 
3330  SCIPfreeBufferArray(scip, &dummy);
3331  }
3332  }
3333  else
3334  {
3335  assert(weights == NULL);
3336  }
3337 
3338  /* create cardinality constraint */
3339  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3340  local, modifiable, dynamic, removable, stickingatnode) );
3341 
3342  consdata->cons = *cons;
3343  assert(consdata->cons != NULL);
3344 
3345  /* replace original variables by transformed variables in transformed constraint, add locks, and catch events */
3346  for( v = nvars - 1; v >= 0; --v )
3347  {
3348  /* always use transformed variables in transformed constraints */
3349  if( transformed )
3350  {
3351  SCIP_CALL( SCIPgetTransformedVar(scip, consdata->vars[v], &(consdata->vars[v])) );
3352  SCIP_CALL( SCIPgetTransformedVar(scip, consdata->indvars[v], &(consdata->indvars[v])) );
3353  }
3354  assert(consdata->vars[v] != NULL);
3355  assert(consdata->indvars[v] != NULL);
3356  assert(transformed == SCIPvarIsTransformed(consdata->vars[v]));
3357  assert(transformed == SCIPvarIsTransformed(consdata->indvars[v]));
3358 
3359  /* handle the new variable */
3360  SCIP_CALL( handleNewVariableCardinality(scip, *cons, consdata, conshdlrdata, consdata->vars[v],
3361  consdata->indvars[v], v, transformed, &consdata->eventdatas[v]) );
3362  assert(! transformed || consdata->eventdatas[v] != NULL);
3363  }
3364 
3365  return SCIP_OKAY;
3366 }
3367 
3368 /** creates and captures a cardinality constraint with all constraint flags set to their default values.
3369  *
3370  * @warning Do NOT set the constraint to be modifiable manually, because this might lead
3371  * to wrong results as the variable array will not be resorted
3372  *
3373  * @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons()
3374  */
3376  SCIP* scip, /**< SCIP data structure */
3377  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3378  const char* name, /**< name of constraint */
3379  int nvars, /**< number of variables in the constraint */
3380  SCIP_VAR** vars, /**< array with variables of constraint entries */
3381  int cardval, /**< number of variables allowed to be nonzero */
3382  SCIP_VAR** indvars, /**< indicator variables indicating which variables may be treated as nonzero
3383  * in cardinality constraint, or NULL if new indicator variables should be
3384  * introduced automatically */
3385  SCIP_Real* weights /**< weights determining the variable order, or NULL if variables should be
3386  * ordered in the same way they were added to the constraint */
3387  )
3388 {
3389  SCIP_CALL( SCIPcreateConsCardinality(scip, cons, name, nvars, vars, cardval, indvars, weights, TRUE, TRUE, TRUE, TRUE,
3390  TRUE, FALSE, FALSE, FALSE, FALSE) );
3391 
3392  return SCIP_OKAY;
3393 }
3394 
3395 /** changes cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */
3397  SCIP* scip, /**< SCIP data structure */
3398  SCIP_CONS* cons, /**< pointer to hold the created constraint */
3399  int cardval /**< number of variables allowed to be nonzero */
3400  )
3401 {
3402  SCIP_CONSDATA* consdata;
3403 
3404  assert(scip != NULL);
3405  assert(cons != NULL);
3406 
3407  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3408  {
3409  SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3410  return SCIP_INVALIDDATA;
3411  }
3412 
3413  consdata = SCIPconsGetData(cons);
3414  assert(consdata != NULL);
3415 
3416  SCIPdebugMsg(scip, "modify right hand side of cardinality constraint from <%i> to <%i>\n", consdata->cardval, cardval);
3417 
3418  /* create constraint data */
3419  consdata->cardval = cardval;
3420 
3421  return SCIP_OKAY;
3422 }
3423 
3424 /** adds variable to cardinality constraint, the position is determined by the given weight */
3426  SCIP* scip, /**< SCIP data structure */
3427  SCIP_CONS* cons, /**< constraint */
3428  SCIP_VAR* var, /**< variable to add to the constraint */
3429  SCIP_VAR* indvar, /**< indicator variable indicating whether variable may be treated as nonzero
3430  * in cardinality constraint (or NULL if this variable should be created
3431  * automatically) */
3432  SCIP_Real weight /**< weight determining position of variable */
3433  )
3434 {
3435  SCIP_CONSHDLRDATA* conshdlrdata;
3436  SCIP_CONSHDLR* conshdlr;
3437 
3438  assert(scip != NULL);
3439  assert(var != NULL);
3440  assert(cons != NULL);
3441 
3442  SCIPdebugMsg(scip, "adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var),
3443  SCIPconsGetName(cons), weight);
3444 
3445  conshdlr = SCIPconsGetHdlr(cons);
3446  assert(conshdlr != NULL);
3447  if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 )
3448  {
3449  SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3450  return SCIP_INVALIDDATA;
3451  }
3452 
3453  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3454  assert(conshdlrdata != NULL);
3455 
3456  SCIP_CALL( addVarCardinality(scip, cons, conshdlrdata, var, indvar, weight) );
3457 
3458  return SCIP_OKAY;
3459 }
3460 
3461 /** appends variable to cardinality constraint */
3463  SCIP* scip, /**< SCIP data structure */
3464  SCIP_CONS* cons, /**< constraint */
3465  SCIP_VAR* var, /**< variable to add to the constraint */
3466  SCIP_VAR* indvar /**< indicator variable indicating whether variable may be treated as nonzero
3467  * in cardinality constraint (or NULL if this variable should be created
3468  * automatically) */
3469  )
3470 {
3471  SCIP_CONSHDLRDATA* conshdlrdata;
3472  SCIP_CONSHDLR* conshdlr;
3473 
3474  assert(scip != NULL);
3475  assert(var != NULL);
3476  assert(cons != NULL);
3477 
3478  SCIPdebugMsg(scip, "appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons));
3479 
3480  conshdlr = SCIPconsGetHdlr(cons);
3481  assert(conshdlr != NULL);
3482  if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 )
3483  {
3484  SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3485  return SCIP_INVALIDDATA;
3486  }
3487 
3488  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3489  assert(conshdlrdata != NULL);
3490 
3491  SCIP_CALL( appendVarCardinality(scip, cons, conshdlrdata, var, indvar) );
3492 
3493  return SCIP_OKAY;
3494 }
3495 
3496 /** gets number of variables in cardinality constraint */
3498  SCIP* scip, /**< SCIP data structure */
3499  SCIP_CONS* cons /**< constraint */
3500  )
3501 {
3502  SCIP_CONSDATA* consdata;
3503 
3504  assert(scip != NULL);
3505  assert(cons != NULL);
3506 
3507  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3508  {
3509  SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3510  SCIPABORT();
3511  return -1; /*lint !e527*/
3512  }
3513 
3514  consdata = SCIPconsGetData(cons);
3515  assert(consdata != NULL);
3516 
3517  return consdata->nvars;
3518 }
3519 
3520 /** gets array of variables in cardinality constraint */
3522  SCIP* scip, /**< SCIP data structure */
3523  SCIP_CONS* cons /**< constraint data */
3524  )
3525 {
3526  SCIP_CONSDATA* consdata;
3527 
3528  assert(scip != NULL);
3529  assert(cons != NULL);
3530 
3531  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3532  {
3533  SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3534  SCIPABORT();
3535  return NULL; /*lint !e527*/
3536  }
3537 
3538  consdata = SCIPconsGetData(cons);
3539  assert(consdata != NULL);
3540 
3541  return consdata->vars;
3542 }
3543 
3544 /** gets cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */
3546  SCIP* scip, /**< SCIP data structure */
3547  SCIP_CONS* cons /**< constraint data */
3548  )
3549 {
3550  SCIP_CONSDATA* consdata;
3551 
3552  assert(scip != NULL);
3553  assert(cons != NULL);
3554 
3555  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3556  {
3557  SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3558  return -1; /*lint !e527*/
3559  }
3560 
3561  consdata = SCIPconsGetData(cons);
3562  assert(consdata != NULL);
3563 
3564  return consdata->cardval;
3565 }
3566 
3567 /** gets array of weights in cardinality constraint (or NULL if not existent) */
3569  SCIP* scip, /**< SCIP data structure */
3570  SCIP_CONS* cons /**< constraint data */
3571  )
3572 {
3573  SCIP_CONSDATA* consdata;
3574 
3575  assert(scip != NULL);
3576  assert(cons != NULL);
3577 
3578  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3579  {
3580  SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3581  SCIPABORT();
3582  return NULL; /*lint !e527*/
3583  }
3584 
3585  consdata = SCIPconsGetData(cons);
3586  assert(consdata != NULL);
3587 
3588  return consdata->weights;
3589 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21909
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:46151
static SCIP_RETCODE handleNewVariableCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_VAR *indvar, int pos, SCIP_Bool transformed, SCIP_EVENTDATA **eventdata)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:21898
#define CONSHDLR_SEPAPRIORITY
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:18829
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip.c:6228
#define EVENTHDLR_NAME
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:21892
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46086
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip.c:40453
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip.c:814
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8140
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c:16958
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip.c:6251
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46099
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip.c:40275
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip.c:6541
void SCIPsortRealPtrPtrInt(SCIP_Real *realarray, void **ptrarray1, void **ptrarray2, int *intarray, int len)
static SCIP_DECL_CONSSEPASOL(consSepasolCardinality)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17166
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip.c:6481
SCIP_Real SCIPgetLocalTransEstimate(SCIP *scip)
Definition: scip.c:13183
#define SCIP_MAXSTRLEN
Definition: def.h:215
SCIP_RETCODE SCIPaddVarCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_VAR *indvar, SCIP_Real weight)
static SCIP_DECL_CONSGETVARS(consGetVarsCardinality)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip.c:5973
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:27962
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12481
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:45601
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c:16946
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:30288
static SCIP_DECL_CONSPRESOL(consPresolCardinality)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:45876
static SCIP_RETCODE fixVariableZeroNode(SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17222
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21781
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip.c:8526
static SCIP_DECL_CONSEXITSOL(consExitsolCardinality)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip.c:18575
static SCIP_RETCODE enforceCardinality(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, SCIP_RESULT *result)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip.c:18384
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16732
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:46175
static SCIP_RETCODE deleteVarCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:16311
#define FALSE
Definition: def.h:64
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:2765
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:278
static SCIP_RETCODE generateRowCardinality(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool local, SCIP_ROW **rowlb, SCIP_ROW **rowub)
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip.c:5831
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip.c:45816
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:9340
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
Definition: scip.c:45888
#define TRUE
Definition: def.h:63
#define SCIPdebug(x)
Definition: pub_message.h:74
#define EVENTHDLR_DESC
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
#define DEFAULT_BRANCHBALANCED
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
Definition: scip.c:21255
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8160
#define CONSHDLR_DESC
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8190
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip.h:21907
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip.c:5885
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21825
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip.h:21933
int SCIPconshdlrGetSepaFreq(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4999
SCIP_RETCODE SCIPchgVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip.c:21611
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2903
static SCIP_DECL_CONSTRANS(consTransCardinality)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:21937
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip.h:21890
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip.c:1010
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8150
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:108
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip.c:6274
#define SCIPdebugMsg
Definition: scip.h:451
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4202
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip.c:1336
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip.c:27146
static SCIP_RETCODE addVarCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_VAR *indvar, SCIP_Real weight)
#define CONSHDLR_DELAYPROP
static SCIP_DECL_CONSPROP(consPropCardinality)
static SCIP_RETCODE appendVarCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *var, SCIP_VAR *indvar)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:16522
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:2997
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:64
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17176
static SCIP_RETCODE fixVariableZero(SCIP *scip, SCIP_VAR *var, SCIP_Bool *infeasible, SCIP_Bool *tightened)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip.h:21904
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
Definition: scip.c:33761
Constraint handler for knapsack constraints of the form , x binary and .
SCIP_Real SCIPeventGetNewbound(SCIP_EVENT *event)
Definition: event.c:1162
SCIP_RETCODE SCIPcreateSolCopy(SCIP *scip, SCIP_SOL **sol, SCIP_SOL *sourcesol)
Definition: scip.c:37295
static SCIP_RETCODE catchVarEventCardinality(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_VAR *indvar, int pos, SCIP_EVENTDATA **eventdata)
SCIP_RETCODE SCIPincludeConshdlrCardinality(SCIP *scip)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip.c:5997
#define SCIPerrorMessage
Definition: pub_message.h:45
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4113
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:12410
static SCIP_RETCODE lockVariableCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_VAR *indvar)
static SCIP_DECL_CONSINITLP(consInitlpCardinality)
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip.c:13111
#define CONSHDLR_MAXPREROUNDS
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip.c:18929
static SCIP_RETCODE branchUnbalancedCardinality(SCIP *scip, SCIP_SOL *sol, SCIP_CONS *branchcons, SCIP_VAR **vars, SCIP_VAR **indvars, int nvars, int cardval, int branchnnonzero, int branchpos)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip.c:45519
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:21383
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCardinality)
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:7881
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:25494
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8100
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:155
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16552
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip.c:6022
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:2798
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4133
static SCIP_DECL_CONSENFORELAX(consEnforelaxCardinality)
#define NULL
Definition: lpi_spx1.cpp:137
#define REALABS(x)
Definition: def.h:159
SCIP_RETCODE SCIPcreateConsKnapsack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Longint *weights, SCIP_Longint capacity, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip.c:36704
static SCIP_DECL_CONSLOCK(consLockCardinality)
#define CONSHDLR_DELAYSEPA
#define SCIP_CALL(x)
Definition: def.h:306
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:63
int SCIPgetNTotalVars(SCIP *scip)
Definition: scip.c:12208
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46125
SCIP_Real SCIPvarGetMultaggrConstant(SCIP_VAR *var)
Definition: var.c:16970
static SCIP_DECL_CONSFREE(consFreeCardinality)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:16321
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8120
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip.c:33869
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:50
static SCIP_RETCODE polishPrimalSolution(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_SOL *primsol)
static SCIP_RETCODE presolRoundCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *success, int *ndelconss, int *nupgdconss, int *nfixedvars, int *nremovedvars)
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip.c:12960
int SCIPgetCardvalCardinality(SCIP *scip, SCIP_CONS *cons)
static SCIP_DECL_CONSENFOLP(consEnfolpCardinality)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:21925
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip.c:37867
static SCIP_DECL_CONSSEPALP(consSepalpCardinality)
static SCIP_RETCODE dropVarEventCardinality(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSDATA *consdata, SCIP_VAR *var, SCIP_VAR *indvar, SCIP_EVENTDATA **eventdata)
SCIP_VAR * SCIPeventGetVar(SCIP_EVENT *event)
Definition: event.c:982
#define CONSHDLR_NAME
#define SCIP_Bool
Definition: def.h:61
static SCIP_DECL_CONSPRINT(consPrintCardinality)
static SCIP_DECL_CONSGETNVARS(consGetNVarsCardinality)
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:959
static SCIP_RETCODE separateCardinality(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, SCIP_RESULT *result)
#define DEFAULT_BALANCEDDEPTH
SCIP_Real * SCIPgetWeightsCardinality(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip.c:30022
int SCIPgetDepth(SCIP *scip)
Definition: scip.c:42094
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip.c:28652
#define MAX(x, y)
Definition: tclique_def.h:75
static SCIP_DECL_CONSENFOPS(consEnfopsCardinality)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:7901
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip.c:37631
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8080
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8050
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip.c:40321
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip.c:36654
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition: scip.c:17237
static SCIP_RETCODE unlockVariableCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_VAR *indvar)
#define CONSHDLR_SEPAFREQ
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip.c:25141
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:89
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip.c:21309
#define CONSHDLR_PROP_TIMING
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip.c:6435
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:65
Constraint handler for linear constraints in their most general form, .
int SCIPvarGetMultaggrNVars(SCIP_VAR *var)
Definition: var.c:16934
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition: scip.c:45827
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
Definition: scip.c:39749
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip.c:36681
static SCIP_RETCODE consdataEnsurevarsSizeCardinality(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveweights)
#define SCIP_REAL_MAX
Definition: def.h:136
static SCIP_RETCODE consdataUnmarkEventdataVars(SCIP_CONSDATA *consdata)
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip.c:30160
#define CONSHDLR_PRESOLTIMING
SCIP_RETCODE SCIPcreateConsCardinality(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int cardval, SCIP_VAR **indvars, SCIP_Real *weights, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45790
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip.c:1911
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition: scip.c:11311
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:7911
#define CONSHDLR_PROPFREQ
constraint handler for cardinality constraints
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip.c:27323
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPcreateConsBasicCardinality(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, int cardval, SCIP_VAR **indvars, SCIP_Real *weights)
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip.c:6190
SCIP_Real SCIPeventGetOldbound(SCIP_EVENT *event)
Definition: event.c:1138
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
Definition: scip.c:46163
static SCIP_RETCODE propCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *nchgdomain)
#define DEFAULT_BALANCEDCUTOFF
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:16671
#define SCIP_Real
Definition: def.h:135
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8130
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip.c:30314
int SCIPgetNVarsCardinality(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip.c:1138
#define MIN(x, y)
Definition: memory.c:75
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip.c:6504
SCIP_RETCODE SCIPchgCardvalCardinality(SCIP *scip, SCIP_CONS *cons, int cardval)
static SCIP_RETCODE initsepaBoundInequalityFromCardinality(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_Bool solvedinitlp, int *ngen, SCIP_Bool *cutoff)
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8070
SCIP_RETCODE SCIPappendVarCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_VAR *indvar)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8060
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip.c:30762
#define SCIP_Longint
Definition: def.h:120
static SCIP_DECL_CONSCOPY(consCopyCardinality)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition: scip.c:45864
SCIP_VAR ** SCIPgetVarsCardinality(SCIP *scip, SCIP_CONS *cons)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:45777
#define CONSHDLR_CHECKPRIORITY
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:49
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17232
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:16694
static SCIP_DECL_EVENTEXEC(eventExecCardinality)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:2846
static SCIP_DECL_CONSCHECK(consCheckCardinality)
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip.c:6118
SCIP_Longint SCIPgetNNodes(SCIP *scip)
Definition: scip.c:41182
#define SCIPABORT()
Definition: def.h:278
static SCIP_RETCODE branchBalancedCardinality(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_CONS *branchcons, SCIP_VAR **vars, SCIP_VAR **indvars, int nvars, int cardval, int branchnnonzero, int branchpos, SCIP_Real balancedcutoff)
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip.c:17353
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip.c:38007
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4258
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
Definition: scip.c:45937
#define CONSHDLR_ENFOPRIORITY
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip.c:4176
static SCIP_DECL_CONSDELETE(consDeleteCardinality)
uint64_t SCIP_EVENTTYPE
Definition: type_event.h:134
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip.c:5931