Scippy

SCIP

Solving Constraint Integer Programs

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