1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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"
74   	#include "symmetry/struct_symmetry.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 */
103  	
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)
109  	
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
156  	SCIP_RETCODE catchVarEventCardinality(
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
191  	SCIP_RETCODE dropVarEventCardinality(
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
222  	SCIP_RETCODE fixVariableZeroNode(
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;
231  	   if( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
232  	   {
233  	      *infeasible = TRUE;
234  	      return SCIP_OKAY;
235  	   }
236  	
237  	   /* if variable is multi-aggregated */
238  	   if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
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
281  	SCIP_RETCODE fixVariableZero(
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  	
296  	   if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
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  	
310  	         SCIP_CALL( SCIPflattenVarAggregationGraph(scip, var) );
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
350  	SCIP_RETCODE lockVariableCardinality(
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
371  	SCIP_RETCODE unlockVariableCardinality(
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 */
383  	   SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)),
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
392  	SCIP_RETCODE consdataEnsurevarsSizeCardinality(
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
434  	SCIP_RETCODE handleNewVariableCardinality(
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
491  	SCIP_RETCODE addVarCardinality(
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
619  	SCIP_RETCODE appendVarCardinality(
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
720  	SCIP_RETCODE deleteVarCardinality(
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
761  	SCIP_RETCODE polishPrimalSolution(
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
808  	void consdataUnmarkEventdataVars(
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
842  	SCIP_RETCODE presolRoundCardinality(
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),
1090 	              SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
1091 	              SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(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
1129 	SCIP_RETCODE propCardinality(
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 */
1194 	            if( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var)) )
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 */
1309 	            if( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
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
1346 	SCIP_RETCODE branchUnbalancedCardinality(
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
1450 	SCIP_RETCODE branchBalancedCardinality(
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
1737 	SCIP_RETCODE enforceCardinality(
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
2006 	SCIP_RETCODE generateRowCardinality(
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
2132 	SCIP_RETCODE initsepaBoundInequalityFromCardinality(
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
2245 	SCIP_RETCODE separateCardinality(
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 */
2300 	   SCIP_CALL( SCIPincludeConshdlrCardinality(scip) );
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;
2312 	
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;
2614 	
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;
2706 	
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;
3110 	
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;
3132 	
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 	
3185 	      SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals,
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( SCIPaddSymgraphVarAggegration(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 	
3214 	      SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals,
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( SCIPaddSymgraphVarAggegration(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 	   return SCIP_OKAY;
3242 	}
3243 	
3244 	/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
3245 	static
3246 	SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphCardinality)
3247 	{  /*lint --e{715}*/
3248 	   SCIP_CONSDATA* consdata;
3249 	   SCIP_VAR** vars;
3250 	   SCIP_Real* vals;
3251 	   SCIP_Real constant;
3252 	   SCIP_Real rhs;
3253 	   int consnodeidx;
3254 	   int pairnodeidx;
3255 	   int nodeidx;
3256 	   int nconsvars;
3257 	   int nlocvars;
3258 	   int nvars;
3259 	   int i;
3260 	
3261 	   consdata = SCIPconsGetData(cons);
3262 	   assert(consdata != NULL);
3263 	   assert(graph != NULL);
3264 	
3265 	   nconsvars = consdata->nvars;
3266 	   rhs = (SCIP_Real) consdata->cardval;
3267 	
3268 	   /* add node for constraint */
3269 	   SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, -SCIPinfinity(scip), rhs, &consnodeidx) );
3270 	
3271 	   /* create nodes and edges for each variable */
3272 	   nvars = SCIPgetNVars(scip);
3273 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3274 	   SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
3275 	
3276 	   for( i = 0; i < nconsvars; ++i )
3277 	   {
3278 	      /* connect each variable and its indicator variable with an intermediate node, which is connected with consnode */
3279 	      SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_CARD_TUPLE , &pairnodeidx) );
3280 	
3281 	      vars[0] = consdata->vars[i];
3282 	      vals[0] = 1.0;
3283 	      nlocvars = 1;
3284 	      constant = 0.0;
3285 	
3286 	      /* use SYM_SYMTYPE_PERM here to NOT center variable domains at 0, as the latter might not preserve
3287 	       * cardinality constraints */
3288 	      SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals,
3289 	            &nlocvars, &constant, SCIPisTransformed(scip)) );
3290 	
3291 	      /* check whether variable is (multi-) aggregated or negated */
3292 	      if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) )
3293 	      {
3294 	         int sumnodeidx;
3295 	         int j;
3296 	
3297 	         /* encode aggregation by a sum-expression */
3298 	         SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &sumnodeidx) ); /*lint !e641*/
3299 	
3300 	         /* we do not need to take weights of variables into account;
3301 	          * they are only used to sort variables within the constraint */
3302 	         SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, sumnodeidx, FALSE, 0.0) );
3303 	
3304 	         /* add nodes and edges for variables in aggregation, do not add edges to negated variables
3305 	          * since this might not necessarily be a symmetry of the cardinality constraint; therefore,
3306 	          * do not use SCIPaddSymgraphVarAggegration() */
3307 	         for( j = 0; j < nlocvars; ++j )
3308 	         {
3309 	            nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[j]);
3310 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, TRUE, vals[j]) );
3311 	         }
3312 	
3313 	         /* possibly add node for constant */
3314 	         if( ! SCIPisZero(scip, constant) )
3315 	         {
3316 	            SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, constant, &nodeidx) );
3317 	
3318 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, FALSE, 0.0) );
3319 	         }
3320 	      }
3321 	      else if( nlocvars == 1 )
3322 	      {
3323 	         SCIP_Bool allownegation = FALSE;
3324 	
3325 	         /* a negation is allowed if it is centered around 0 */
3326 	         if ( SCIPisInfinity(scip, -SCIPvarGetLbGlobal(vars[0])) == SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[0]))
3327 	            && (SCIPisInfinity(scip, SCIPvarGetUbGlobal(vars[0]))
3328 	               || SCIPisZero(scip, (SCIPvarGetLbGlobal(vars[0]) + SCIPvarGetUbGlobal(vars[0]))/2)) )
3329 	            allownegation = TRUE;
3330 	
3331 	         nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]);
3332 	         SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, TRUE, 1.0) );
3333 	
3334 	         nodeidx = SCIPgetSymgraphNegatedVarnodeidx(scip, graph, vars[0]);
3335 	         if( allownegation )
3336 	         {
3337 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, TRUE, 1.0) );
3338 	         }
3339 	         else
3340 	         {
3341 	            SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
3342 	         }
3343 	      }
3344 	
3345 	      /* connect indicator variable with pair node, do not add edges to negated variables since negating
3346 	       * might not preserve the cardinality requirement
3347 	       */
3348 	      vars[0] = consdata->indvars[i];
3349 	      vals[0] = 1.0;
3350 	      nlocvars = 1;
3351 	      constant = 0.0;
3352 	
3353 	      SCIP_CALL( SCIPgetActiveVariables(scip, SYM_SYMTYPE_PERM, &vars, &vals,
3354 	            &nlocvars, &constant, SCIPisTransformed(scip)) );
3355 	
3356 	      /* check whether variable is (multi-)aggregated or negated */
3357 	      if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) )
3358 	      {
3359 	         /* encode aggregation by a sum-expression */
3360 	         SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/
3361 	
3362 	         /* we do not need to take weights of variables into account;
3363 	          * they are only used to sort variables within the constraint */
3364 	         SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
3365 	
3366 	         /* add nodes and edges for variables in aggregation */
3367 	         SCIP_CALL( SCIPaddSymgraphVarAggegration(scip, graph, nodeidx, vars, vals, nlocvars, constant) );
3368 	      }
3369 	      else if( nlocvars == 1 )
3370 	      {
3371 	         nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]);
3372 	
3373 	         SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
3374 	      }
3375 	   }
3376 	
3377 	   SCIPfreeBufferArray(scip, &vals);
3378 	   SCIPfreeBufferArray(scip, &vars);
3379 	
3380 	   return SCIP_OKAY;
3381 	}
3382 	
3383 	/* ---------------- Callback methods of event handler ---------------- */
3384 	
3385 	/* exec the event handler
3386 	 *
3387 	 * update the number of variables fixed to be nonzero
3388 	 * update the bound constraints
3389 	 */
3390 	static
3391 	SCIP_DECL_EVENTEXEC(eventExecCardinality)
3392 	{
3393 	   SCIP_EVENTTYPE eventtype;
3394 	   SCIP_CONSDATA* consdata;
3395 	   SCIP_Real oldbound;
3396 	   SCIP_Real newbound;
3397 	   SCIP_VAR* var;
3398 	
3399 	   assert(eventhdlr != NULL);
3400 	   assert(eventdata != NULL);
3401 	   assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3402 	   assert(event != NULL);
3403 	
3404 	   consdata = eventdata->consdata;
3405 	   assert(consdata != NULL);
3406 	   assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3407 	   assert(consdata->eventdatascurrent != NULL);
3408 	   assert(consdata->eventvarscurrent != NULL);
3409 	
3410 	   var = SCIPeventGetVar(event);
3411 	   assert(var != NULL);
3412 	   oldbound = SCIPeventGetOldbound(event);
3413 	   newbound = SCIPeventGetNewbound(event);
3414 	   eventtype = SCIPeventGetType(event);
3415 	
3416 	#ifdef SCIP_DEBUG
3417 	   if( ( eventdata->varmarked && var == eventdata->var) || ( eventdata->indvarmarked && var == eventdata->indvar)  )
3418 	   {
3419 	      int i;
3420 	
3421 	      for( i = 0; i < consdata->neventdatascurrent; ++i )
3422 	      {
3423 	         if( var == consdata->eventvarscurrent[i] )
3424 	         {
3425 	            break;
3426 	         }
3427 	      }
3428 	      assert(i < consdata->neventdatascurrent);
3429 	   }
3430 	#endif
3431 	
3432 	   if( eventtype & SCIP_EVENTTYPE_GBDCHANGED )
3433 	   {
3434 	      if( eventtype == SCIP_EVENTTYPE_GLBCHANGED )
3435 	      {
3436 	         /* global lower bound is not negative anymore -> remove down lock */
3437 	         if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) )
3438 	            SCIP_CALL( SCIPunlockVarCons(scip, var, consdata->cons, TRUE, FALSE) );
3439 	         /* global lower bound turned negative -> add down lock */
3440 	         else if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
3441 	            SCIP_CALL( SCIPlockVarCons(scip, var, consdata->cons, TRUE, FALSE) );
3442 	
3443 	         return SCIP_OKAY;
3444 	      }
3445 	      if( eventtype == SCIP_EVENTTYPE_GUBCHANGED )
3446 	      {
3447 	         /* global upper bound is not positive anymore -> remove up lock */
3448 	         if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) )
3449 	            SCIP_CALL( SCIPunlockVarCons(scip, var, consdata->cons, FALSE, TRUE) );
3450 	         /* global upper bound turned positive -> add up lock */
3451 	         else if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
3452 	            SCIP_CALL( SCIPlockVarCons(scip, var, consdata->cons, FALSE, TRUE) );
3453 	
3454 	         return SCIP_OKAY;
3455 	      }
3456 	   }
3457 	
3458 	   /* if variable is an indicator variable */
3459 	   if( var == eventdata->indvar )
3460 	   {
3461 	      assert(SCIPvarIsBinary(var));
3462 	      assert(consdata->cons != NULL);
3463 	
3464 	      if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED )
3465 	         ++(consdata->ntreatnonzeros);
3466 	      else if( eventtype == SCIP_EVENTTYPE_LBRELAXED )
3467 	         --(consdata->ntreatnonzeros);
3468 	      else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED && ! eventdata->indvarmarked )
3469 	      {
3470 	         assert(oldbound == 1.0 && newbound == 0.0 );
3471 	
3472 	         /* save event data for propagation */
3473 	         consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3474 	         consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3475 	         ++consdata->neventdatascurrent;
3476 	         eventdata->indvarmarked = TRUE;
3477 	         assert(consdata->neventdatascurrent <= 4 * consdata->maxvars);
3478 	         assert(var == eventdata->indvar );
3479 	      }
3480 	      assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3481 	   }
3482 	
3483 	   /* if variable is an implied variable,
3484 	    * notice that the case consdata->var = consdata->indvar is possible */
3485 	   if( var == eventdata->var && ! eventdata->varmarked )
3486 	   {
3487 	      if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED )
3488 	      {
3489 	         /* if variable is now fixed to be nonzero */
3490 	         if( !SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
3491 	         {
3492 	            /* save event data for propagation */
3493 	            consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3494 	            consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3495 	            ++consdata->neventdatascurrent;
3496 	            eventdata->varmarked = TRUE;
3497 	            assert(consdata->neventdatascurrent <= 4 * consdata->maxvars );
3498 	            assert(var == eventdata->var );
3499 	         }
3500 	      }
3501 	      else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED )
3502 	      {
3503 	         /* if variable is now fixed to be nonzero */
3504 	         if( !SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
3505 	         {
3506 	            /* save event data for propagation */
3507 	            consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3508 	            consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3509 	            ++consdata->neventdatascurrent;
3510 	            eventdata->varmarked = TRUE;
3511 	            assert(consdata->neventdatascurrent <= 4 * consdata->maxvars );
3512 	            assert(var == eventdata->var);
3513 	         }
3514 	      }
3515 	   }
3516 	   assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3517 	
3518 	   SCIPdebugMsg(scip, "event exec cons <%s>: changed bound of variable <%s> from %f to %f (ntreatnonzeros: %d).\n",
3519 	        SCIPconsGetName(consdata->cons), SCIPvarGetName(SCIPeventGetVar(event)),
3520 	        oldbound, newbound, consdata->ntreatnonzeros);
3521 	
3522 	   return SCIP_OKAY;
3523 	}
3524 	
3525 	/* ---------------- Constraint specific interface methods ---------------- */
3526 	
3527 	/** creates the handler for cardinality constraints and includes it in SCIP */
3528 	SCIP_RETCODE SCIPincludeConshdlrCardinality(
3529 	   SCIP*                 scip                /**< SCIP data structure */
3530 	   )
3531 	{
3532 	   SCIP_CONSHDLRDATA* conshdlrdata;
3533 	   SCIP_CONSHDLR* conshdlr;
3534 	
3535 	   /* create constraint handler data */
3536 	   SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3537 	   conshdlrdata->eventhdlr = NULL;
3538 	   conshdlrdata->varhash = NULL;
3539 	
3540 	   /* create event handler for bound change events */
3541 	   SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &conshdlrdata->eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3542 	        eventExecCardinality, NULL) );
3543 	   if( conshdlrdata->eventhdlr == NULL )
3544 	   {
3545 	      SCIPerrorMessage("event handler for cardinality constraints not found.\n");
3546 	      return SCIP_PLUGINNOTFOUND;
3547 	   }
3548 	
3549 	   /* include constraint handler */
3550 	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
3551 	         CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
3552 	         consEnfolpCardinality, consEnfopsCardinality, consCheckCardinality, consLockCardinality, conshdlrdata) );
3553 	   assert(conshdlr != NULL);
3554 	
3555 	   /* set non-fundamental callbacks via specific setter functions */
3556 	   SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyCardinality, consCopyCardinality) );
3557 	   SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteCardinality) );
3558 	   SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolCardinality) );
3559 	   SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeCardinality) );
3560 	   SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsCardinality) );
3561 	   SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsCardinality) );
3562 	   SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpCardinality) );
3563 	   SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseCardinality) );
3564 	   SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolCardinality, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3565 	   SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintCardinality) );
3566 	   SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropCardinality, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3567 	        CONSHDLR_PROP_TIMING) );
3568 	   /*SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropCardinality) ); @todo: implement repropagation */
3569 	   SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCardinality, consSepasolCardinality, CONSHDLR_SEPAFREQ,
3570 	        CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
3571 	   SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransCardinality) );
3572 	   SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxCardinality) );
3573 	   SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphCardinality) );
3574 	   SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphCardinality) );
3575 	
3576 	   /* add cardinality constraint handler parameters */
3577 	   SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/branchbalanced",
3578 	         "whether to use balanced instead of unbalanced branching",
3579 	         &conshdlrdata->branchbalanced, TRUE, DEFAULT_BRANCHBALANCED, NULL, NULL) );
3580 	
3581 	   SCIP_CALL( SCIPaddIntParam(scip, "constraints/" CONSHDLR_NAME "/balanceddepth",
3582 	         "maximum depth for using balanced branching (-1: no limit)",
3583 	         &conshdlrdata->balanceddepth, TRUE, DEFAULT_BALANCEDDEPTH, -1, INT_MAX, NULL, NULL) );
3584 	
3585 	   SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/balancedcutoff",
3586 	         "determines that balanced branching is only used if the branching cut off value "
3587 	         "w.r.t. the current LP solution is greater than a given value",
3588 	         &conshdlrdata->balancedcutoff, TRUE, DEFAULT_BALANCEDCUTOFF, 0.01, SCIP_REAL_MAX, NULL, NULL) );
3589 	
3590 	   return SCIP_OKAY;
3591 	}
3592 	
3593 	/** creates and captures a cardinality constraint
3594 	 *
3595 	 *  We set the constraint to not be modifable. If the weights are non
3596 	 *  NULL, the variables are ordered according to these weights (in
3597 	 *  ascending order).
3598 	 *
3599 	 *  @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons()
3600 	 */
3601 	SCIP_RETCODE SCIPcreateConsCardinality(
3602 	   SCIP*                 scip,               /**< SCIP data structure */
3603 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
3604 	   const char*           name,               /**< name of constraint */
3605 	   int                   nvars,              /**< number of variables in the constraint */
3606 	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
3607 	   int                   cardval,            /**< number of variables allowed to be nonzero */
3608 	   SCIP_VAR**            indvars,            /**< indicator variables indicating which variables may be treated as nonzero
3609 	                                              *   in cardinality constraint, or NULL if new indicator variables should be
3610 	                                              *   introduced automatically */
3611 	   SCIP_Real*            weights,            /**< weights determining the variable order, or NULL if variables should be
3612 	                                              *   ordered in the same way they were added to the constraint */
3613 	   SCIP_Bool             initial,            /**< should the LP relaxation of constraint be in the initial LP?
3614 	                                              *   Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3615 	   SCIP_Bool             separate,           /**< should the constraint be separated during LP processing?
3616 	                                              *   Usually set to TRUE. */
3617 	   SCIP_Bool             enforce,            /**< should the constraint be enforced during node processing?
3618 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
3619 	   SCIP_Bool             check,              /**< should the constraint be checked for feasibility?
3620 	                                              *   TRUE for model constraints, FALSE for additional, redundant constraints. */
3621 	   SCIP_Bool             propagate,          /**< should the constraint be propagated during node processing?
3622 	                                              *   Usually set to TRUE. */
3623 	   SCIP_Bool             local,              /**< is constraint only valid locally?
3624 	                                              *   Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3625 	   SCIP_Bool             dynamic,            /**< is constraint subject to aging?
3626 	                                              *   Usually set to FALSE. Set to TRUE for own cuts which
3627 	                                              *   are separated as constraints. */
3628 	   SCIP_Bool             removable,          /**< should the relaxation be removed from the LP due to aging or cleanup?
3629 	                                              *   Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3630 	   SCIP_Bool             stickingatnode      /**< should the constraint always be kept at the node where it was added, even
3631 	                                              *   if it may be moved to a more global node?
3632 	                                              *   Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3633 	   )
3634 	{
3635 	   SCIP_CONSHDLRDATA* conshdlrdata;
3636 	   SCIP_CONSHDLR* conshdlr;
3637 	   SCIP_CONSDATA* consdata;
3638 	   SCIP_Bool modifiable;
3639 	   SCIP_Bool transformed;
3640 	   int v;
3641 	
3642 	   modifiable = FALSE;
3643 	
3644 	   /* find the cardinality constraint handler */
3645 	   conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3646 	   if( conshdlr == NULL )
3647 	   {
3648 	      SCIPerrorMessage("<%s> constraint handler not found\n", CONSHDLR_NAME);
3649 	      return SCIP_PLUGINNOTFOUND;
3650 	   }
3651 	
3652 	   /* get constraint handler data */
3653 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
3654 	   assert(conshdlrdata != NULL);
3655 	
3656 	   /* are we in the transformed problem? */
3657 	   transformed = SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED;
3658 	
3659 	   /* create constraint data */
3660 	   SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
3661 	   consdata->cons = NULL;
3662 	   consdata->vars = NULL;
3663 	   consdata->indvars = NULL;
3664 	   consdata->eventdatas = NULL;
3665 	   consdata->nvars = nvars;
3666 	   consdata->cardval = cardval;
3667 	   consdata->maxvars = nvars;
3668 	   consdata->rowub = NULL;
3669 	   consdata->rowlb = NULL;
3670 	   consdata->eventdatascurrent = NULL;
3671 	   consdata->eventvarscurrent = NULL;
3672 	   consdata->neventdatascurrent = 0;
3673 	   consdata->ntreatnonzeros = transformed ? 0 : -1;
3674 	   consdata->weights = NULL;
3675 	
3676 	   if( nvars > 0 )
3677 	   {
3678 	      /* duplicate memory for implied variables */
3679 	      SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->vars, vars, nvars) );
3680 	
3681 	      /* create indicator variables if not present */
3682 	      if( indvars != NULL )
3683 	      {
3684 	         SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->indvars, indvars, nvars) );
3685 	      }
3686 	      else
3687 	      {
3688 	         if( conshdlrdata->varhash == NULL )
3689 	         {
3690 	            /* set up hash map */
3691 	            SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) );
3692 	         }
3693 	
3694 	         SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->indvars, nvars) );
3695 	         for( v = 0; v < nvars; ++v )
3696 	         {
3697 	            SCIP_VAR* implvar;
3698 	
3699 	            implvar = vars[v];
3700 	            assert(implvar != NULL);
3701 	
3702 	            /* check whether an indicator variable already exists for implied variable */
3703 	            if( SCIPhashmapExists(conshdlrdata->varhash, implvar) )
3704 	            {
3705 	               assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar) != NULL);
3706 	               consdata->indvars[v] = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar);
3707 	            }
3708 	            else
3709 	            {
3710 	               /* if implied variable is binary, then it is not necessary to create an indicator variable */
3711 	               if( SCIPvarIsBinary(implvar) )
3712 	                  consdata->indvars[v] = implvar;
3713 	               else
3714 	               {
3715 	                  char varname[SCIP_MAXSTRLEN];
3716 	                  SCIP_VAR* var;
3717 	
3718 	                  (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(vars[v]));
3719 	                  SCIP_CALL( SCIPcreateVar(scip, &var, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE,
3720 	                        NULL, NULL, NULL, NULL, NULL) );
3721 	                  SCIP_CALL( SCIPaddVar(scip, var) );
3722 	                  consdata->indvars[v] = var;
3723 	                  SCIP_CALL( SCIPreleaseVar(scip, &var) );
3724 	               }
3725 	
3726 	               /* insert implied variable to hash map */
3727 	               SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, implvar, (void*) consdata->indvars[v]) );/*lint !e571*/
3728 	               assert(consdata->indvars[v] == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar));
3729 	               assert(SCIPhashmapExists(conshdlrdata->varhash, implvar));
3730 	            }
3731 	         }
3732 	      }
3733 	
3734 	      /* allocate block memory */
3735 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*nvars) );/*lint !e647*/
3736 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*nvars) );/*lint !e647*/
3737 	      SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatas, nvars) );
3738 	
3739 	      /* check weights */
3740 	      if( weights != NULL )
3741 	      {
3742 	         int* dummy;
3743 	
3744 	         /* store weights */
3745 	         SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, weights, nvars) );
3746 	
3747 	         /* create dummy array to make code compatible with SCIP 3.2.0
3748 	          * (the function SCIPsortRealPtrPtr() is not available) */
3749 	         SCIP_CALL( SCIPallocBufferArray(scip, &dummy, nvars) );
3750 	         for( v = 0; v < nvars; ++v )
3751 	            dummy[v] = 0;
3752 	
3753 	         /* sort variables - ascending order */
3754 	         SCIPsortRealPtrPtrInt(consdata->weights, (void**)consdata->vars, (void**)consdata->indvars, dummy, nvars);
3755 	
3756 	         SCIPfreeBufferArray(scip, &dummy);
3757 	      }
3758 	   }
3759 	   else
3760 	   {
3761 	      assert(weights == NULL);
3762 	   }
3763 	
3764 	   /* create cardinality constraint */
3765 	   SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3766 	         local, modifiable, dynamic, removable, stickingatnode) );
3767 	
3768 	   consdata->cons = *cons;
3769 	   assert(consdata->cons != NULL);
3770 	
3771 	   /* replace original variables by transformed variables in transformed constraint, add locks, and catch events */
3772 	   for( v = nvars - 1; v >= 0; --v )
3773 	   {
3774 	      /* always use transformed variables in transformed constraints */
3775 	      if( transformed )
3776 	      {
3777 	         SCIP_CALL( SCIPgetTransformedVar(scip, consdata->vars[v], &(consdata->vars[v])) );
3778 	         SCIP_CALL( SCIPgetTransformedVar(scip, consdata->indvars[v], &(consdata->indvars[v])) );
3779 	      }
3780 	      assert(consdata->vars[v] != NULL);
3781 	      assert(consdata->indvars[v] != NULL);
3782 	      assert(transformed == SCIPvarIsTransformed(consdata->vars[v]));
3783 	      assert(transformed == SCIPvarIsTransformed(consdata->indvars[v]));
3784 	
3785 	      /* handle the new variable */
3786 	      SCIP_CALL( handleNewVariableCardinality(scip, *cons, consdata, conshdlrdata, consdata->vars[v],
3787 	           consdata->indvars[v], v, transformed, &consdata->eventdatas[v]) );
3788 	      assert(! transformed || consdata->eventdatas[v] != NULL);
3789 	   }
3790 	
3791 	   return SCIP_OKAY;
3792 	}
3793 	
3794 	/** creates and captures a cardinality constraint with all constraint flags set to their default values.
3795 	 *
3796 	 *  @warning Do NOT set the constraint to be modifiable manually, because this might lead
3797 	 *  to wrong results as the variable array will not be resorted
3798 	 *
3799 	 *  @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons()
3800 	 */
3801 	SCIP_RETCODE SCIPcreateConsBasicCardinality(
3802 	   SCIP*                 scip,               /**< SCIP data structure */
3803 	   SCIP_CONS**           cons,               /**< pointer to hold the created constraint */
3804 	   const char*           name,               /**< name of constraint */
3805 	   int                   nvars,              /**< number of variables in the constraint */
3806 	   SCIP_VAR**            vars,               /**< array with variables of constraint entries */
3807 	   int                   cardval,            /**< number of variables allowed to be nonzero */
3808 	   SCIP_VAR**            indvars,            /**< indicator variables indicating which variables may be treated as nonzero
3809 	                                              *   in cardinality constraint, or NULL if new indicator variables should be
3810 	                                              *   introduced automatically */
3811 	   SCIP_Real*            weights             /**< weights determining the variable order, or NULL if variables should be
3812 	                                              *   ordered in the same way they were added to the constraint */
3813 	   )
3814 	{
3815 	   SCIP_CALL( SCIPcreateConsCardinality(scip, cons, name, nvars, vars, cardval, indvars, weights, TRUE, TRUE, TRUE, TRUE,
3816 	        TRUE, FALSE, FALSE, FALSE, FALSE) );
3817 	
3818 	   return SCIP_OKAY;
3819 	}
3820 	
3821 	/** changes cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */
3822 	SCIP_RETCODE  SCIPchgCardvalCardinality(
3823 	   SCIP*                 scip,               /**< SCIP data structure */
3824 	   SCIP_CONS*            cons,               /**< pointer to hold the created constraint */
3825 	   int                   cardval             /**< number of variables allowed to be nonzero */
3826 	   )
3827 	{
3828 	   SCIP_CONSDATA* consdata;
3829 	
3830 	   assert(scip != NULL);
3831 	   assert(cons != NULL);
3832 	
3833 	   if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3834 	   {
3835 	      SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3836 	      return SCIP_INVALIDDATA;
3837 	   }
3838 	
3839 	   consdata = SCIPconsGetData(cons);
3840 	   assert(consdata != NULL);
3841 	
3842 	   SCIPdebugMsg(scip, "modify right hand side of cardinality constraint from <%i> to <%i>\n", consdata->cardval, cardval);
3843 	
3844 	   /* create constraint data */
3845 	   consdata->cardval = cardval;
3846 	
3847 	   return SCIP_OKAY;
3848 	}
3849 	
3850 	/** adds variable to cardinality constraint, the position is determined by the given weight */
3851 	SCIP_RETCODE SCIPaddVarCardinality(
3852 	   SCIP*                 scip,               /**< SCIP data structure */
3853 	   SCIP_CONS*            cons,               /**< constraint */
3854 	   SCIP_VAR*             var,                /**< variable to add to the constraint */
3855 	   SCIP_VAR*             indvar,             /**< indicator variable indicating whether variable may be treated as nonzero
3856 	                                              *   in cardinality constraint (or NULL if this variable should be created
3857 	                                              *   automatically) */
3858 	   SCIP_Real             weight              /**< weight determining position of variable */
3859 	   )
3860 	{
3861 	   SCIP_CONSHDLRDATA* conshdlrdata;
3862 	   SCIP_CONSHDLR* conshdlr;
3863 	
3864 	   assert(scip != NULL);
3865 	   assert(var != NULL);
3866 	   assert(cons != NULL);
3867 	
3868 	   SCIPdebugMsg(scip, "adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var),
3869 	        SCIPconsGetName(cons), weight);
3870 	
3871 	   conshdlr = SCIPconsGetHdlr(cons);
3872 	   assert(conshdlr != NULL);
3873 	   if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 )
3874 	   {
3875 	      SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3876 	      return SCIP_INVALIDDATA;
3877 	   }
3878 	
3879 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
3880 	   assert(conshdlrdata != NULL);
3881 	
3882 	   SCIP_CALL( addVarCardinality(scip, cons, conshdlrdata, var, indvar, weight) );
3883 	
3884 	   return SCIP_OKAY;
3885 	}
3886 	
3887 	/** appends variable to cardinality constraint */
3888 	SCIP_RETCODE SCIPappendVarCardinality(
3889 	   SCIP*                 scip,               /**< SCIP data structure */
3890 	   SCIP_CONS*            cons,               /**< constraint */
3891 	   SCIP_VAR*             var,                /**< variable to add to the constraint */
3892 	   SCIP_VAR*             indvar              /**< indicator variable indicating whether variable may be treated as nonzero
3893 	                                              *   in cardinality constraint (or NULL if this variable should be created
3894 	                                              *   automatically) */
3895 	   )
3896 	{
3897 	   SCIP_CONSHDLRDATA* conshdlrdata;
3898 	   SCIP_CONSHDLR* conshdlr;
3899 	
3900 	   assert(scip != NULL);
3901 	   assert(var != NULL);
3902 	   assert(cons != NULL);
3903 	
3904 	   SCIPdebugMsg(scip, "appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons));
3905 	
3906 	   conshdlr = SCIPconsGetHdlr(cons);
3907 	   assert(conshdlr != NULL);
3908 	   if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 )
3909 	   {
3910 	      SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3911 	      return SCIP_INVALIDDATA;
3912 	   }
3913 	
3914 	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
3915 	   assert(conshdlrdata != NULL);
3916 	
3917 	   SCIP_CALL( appendVarCardinality(scip, cons, conshdlrdata, var, indvar) );
3918 	
3919 	   return SCIP_OKAY;
3920 	}
3921 	
3922 	/** gets number of variables in cardinality constraint */
3923 	int SCIPgetNVarsCardinality(
3924 	   SCIP*                 scip,               /**< SCIP data structure */
3925 	   SCIP_CONS*            cons                /**< constraint */
3926 	   )
3927 	{
3928 	   SCIP_CONSDATA* consdata;
3929 	
3930 	   assert(scip != NULL);
3931 	   assert(cons != NULL);
3932 	
3933 	   if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3934 	   {
3935 	      SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3936 	      SCIPABORT();
3937 	      return -1;  /*lint !e527*/
3938 	   }
3939 	
3940 	   consdata = SCIPconsGetData(cons);
3941 	   assert(consdata != NULL);
3942 	
3943 	   return consdata->nvars;
3944 	}
3945 	
3946 	/** gets array of variables in cardinality constraint */
3947 	SCIP_VAR** SCIPgetVarsCardinality(
3948 	   SCIP*                 scip,               /**< SCIP data structure */
3949 	   SCIP_CONS*            cons                /**< constraint data */
3950 	   )
3951 	{
3952 	   SCIP_CONSDATA* consdata;
3953 	
3954 	   assert(scip != NULL);
3955 	   assert(cons != NULL);
3956 	
3957 	   if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3958 	   {
3959 	      SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3960 	      SCIPABORT();
3961 	      return NULL;  /*lint !e527*/
3962 	   }
3963 	
3964 	   consdata = SCIPconsGetData(cons);
3965 	   assert(consdata != NULL);
3966 	
3967 	   return consdata->vars;
3968 	}
3969 	
3970 	/** gets cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */
3971 	int SCIPgetCardvalCardinality(
3972 	   SCIP*                 scip,               /**< SCIP data structure */
3973 	   SCIP_CONS*            cons                /**< constraint data */
3974 	   )
3975 	{
3976 	   SCIP_CONSDATA* consdata;
3977 	
3978 	   assert(scip != NULL);
3979 	   assert(cons != NULL);
3980 	
3981 	   if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3982 	   {
3983 	      SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3984 	      return -1;  /*lint !e527*/
3985 	   }
3986 	
3987 	   consdata = SCIPconsGetData(cons);
3988 	   assert(consdata != NULL);
3989 	
3990 	   return consdata->cardval;
3991 	}
3992 	
3993 	/** gets array of weights in cardinality constraint (or NULL if not existent) */
3994 	SCIP_Real* SCIPgetWeightsCardinality(
3995 	   SCIP*                 scip,               /**< SCIP data structure */
3996 	   SCIP_CONS*            cons                /**< constraint data */
3997 	   )
3998 	{
3999 	   SCIP_CONSDATA* consdata;
4000 	
4001 	   assert(scip != NULL);
4002 	   assert(cons != NULL);
4003 	
4004 	   if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4005 	   {
4006 	      SCIPerrorMessage("constraint is not a cardinality constraint.\n");
4007 	      SCIPABORT();
4008 	      return NULL;  /*lint !e527*/
4009 	   }
4010 	
4011 	   consdata = SCIPconsGetData(cons);
4012 	   assert(consdata != NULL);
4013 	
4014 	   return consdata->weights;
4015 	}
4016