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