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