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