1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit 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? */
83
84 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
85 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
86
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 */
92
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)
98
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
catchVarEventCardinality(SCIP * scip,SCIP_EVENTHDLR * eventhdlr,SCIP_CONSDATA * consdata,SCIP_VAR * var,SCIP_VAR * indvar,int pos,SCIP_EVENTDATA ** eventdata)145 SCIP_RETCODE catchVarEventCardinality(
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
dropVarEventCardinality(SCIP * scip,SCIP_EVENTHDLR * eventhdlr,SCIP_CONSDATA * consdata,SCIP_VAR * var,SCIP_VAR * indvar,SCIP_EVENTDATA ** eventdata)180 SCIP_RETCODE dropVarEventCardinality(
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
fixVariableZeroNode(SCIP * scip,SCIP_VAR * var,SCIP_NODE * node,SCIP_Bool * infeasible)211 SCIP_RETCODE fixVariableZeroNode(
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;
220 if( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
221 {
222 *infeasible = TRUE;
223 return SCIP_OKAY;
224 }
225
226 /* if variable is multi-aggregated */
227 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
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
fixVariableZero(SCIP * scip,SCIP_VAR * var,SCIP_Bool * infeasible,SCIP_Bool * tightened)270 SCIP_RETCODE fixVariableZero(
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
285 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
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
299 SCIP_CALL( SCIPflattenVarAggregationGraph(scip, var) );
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
lockVariableCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_VAR * var,SCIP_VAR * indvar)339 SCIP_RETCODE lockVariableCardinality(
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
unlockVariableCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_VAR * var,SCIP_VAR * indvar)360 SCIP_RETCODE unlockVariableCardinality(
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 */
372 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, SCIPisFeasNegative(scip, SCIPvarGetLbGlobal(var)),
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
consdataEnsurevarsSizeCardinality(SCIP * scip,SCIP_CONSDATA * consdata,int num,SCIP_Bool reserveweights)381 SCIP_RETCODE consdataEnsurevarsSizeCardinality(
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
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)423 SCIP_RETCODE handleNewVariableCardinality(
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
addVarCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_CONSHDLRDATA * conshdlrdata,SCIP_VAR * var,SCIP_VAR * indvar,SCIP_Real weight)480 SCIP_RETCODE addVarCardinality(
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) );
538 SCIP_CALL( SCIPaddVar(scip, newvar) );
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
appendVarCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_CONSHDLRDATA * conshdlrdata,SCIP_VAR * var,SCIP_VAR * indvar)608 SCIP_RETCODE appendVarCardinality(
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) );
657 SCIP_CALL( SCIPaddVar(scip, newvar) );
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
deleteVarCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_CONSDATA * consdata,SCIP_EVENTHDLR * eventhdlr,int pos)709 SCIP_RETCODE deleteVarCardinality(
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
polishPrimalSolution(SCIP * scip,SCIP_CONS ** conss,int nconss,SCIP_SOL * sol,SCIP_SOL * primsol)750 SCIP_RETCODE polishPrimalSolution(
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
consdataUnmarkEventdataVars(SCIP_CONSDATA * consdata)797 void consdataUnmarkEventdataVars(
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
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)831 SCIP_RETCODE presolRoundCardinality(
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),
1079 SCIPconsIsEnforced(cons), SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
1080 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
1081 SCIPconsIsStickingAtNode(cons)) );/*lint !e524*/
1082 SCIP_CALL( SCIPaddCons(scip, knapsackcons) );
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
propCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_CONSDATA * consdata,SCIP_Bool * cutoff,int * nchgdomain)1118 SCIP_RETCODE propCardinality(
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 */
1177 if( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var)) )
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 */
1292 if( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(var)) )
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
branchUnbalancedCardinality(SCIP * scip,SCIP_SOL * sol,SCIP_CONS * branchcons,SCIP_VAR ** vars,SCIP_VAR ** indvars,int nvars,int cardval,int branchnnonzero,int branchpos)1329 SCIP_RETCODE branchUnbalancedCardinality(
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
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)1430 SCIP_RETCODE branchBalancedCardinality(
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[
1709 * |\mbox{supp}(x_{d_1}, \ldots, x_{d_r})| \leq s \qquad \mbox{and}\qquad
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
enforceCardinality(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_SOL * sol,int nconss,SCIP_CONS ** conss,SCIP_RESULT * result)1717 SCIP_RETCODE enforceCardinality(
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[
1972 * \frac{x_1}{u_1} + \ldots + \frac{x_n}{u_n} \leq k\qquad\mbox{and}\qquad
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
generateRowCardinality(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_CONS * cons,SCIP_Bool local,SCIP_ROW ** rowlb,SCIP_ROW ** rowub)1986 SCIP_RETCODE generateRowCardinality(
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
initsepaBoundInequalityFromCardinality(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_CONS ** conss,int nconss,SCIP_SOL * sol,SCIP_Bool solvedinitlp,int * ngen,SCIP_Bool * cutoff)2112 SCIP_RETCODE initsepaBoundInequalityFromCardinality(
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
separateCardinality(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_SOL * sol,int nconss,SCIP_CONS ** conss,SCIP_RESULT * result)2225 SCIP_RETCODE separateCardinality(
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
SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCardinality)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 */
2280 SCIP_CALL( SCIPincludeConshdlrCardinality(scip) );
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
SCIP_DECL_CONSFREE(consFreeCardinality)2289 SCIP_DECL_CONSFREE(consFreeCardinality)
2290 {
2291 SCIP_CONSHDLRDATA* conshdlrdata;
2292
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
SCIP_DECL_CONSEXITSOL(consExitsolCardinality)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
SCIP_DECL_CONSDELETE(consDeleteCardinality)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
SCIP_DECL_CONSTRANS(consTransCardinality)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
SCIP_DECL_CONSPRESOL(consPresolCardinality)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
SCIP_DECL_CONSINITLP(consInitlpCardinality)2591 SCIP_DECL_CONSINITLP(consInitlpCardinality)
2592 { /*lint --e{715}*/
2593 SCIP_Bool cutoff;
2594
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
SCIP_DECL_CONSSEPALP(consSepalpCardinality)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
SCIP_DECL_CONSSEPASOL(consSepasolCardinality)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
SCIP_DECL_CONSENFOLP(consEnfolpCardinality)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
SCIP_DECL_CONSENFORELAX(consEnforelaxCardinality)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
SCIP_DECL_CONSENFOPS(consEnfopsCardinality)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
SCIP_DECL_CONSCHECK(consCheckCardinality)2683 SCIP_DECL_CONSCHECK(consCheckCardinality)
2684 { /*lint --e{715}*/
2685 int c;
2686
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 )
2741 SCIPupdateSolConsViolation(scip, sol, 1.0, 1.0);
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
SCIP_DECL_CONSPROP(consPropCardinality)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
SCIP_DECL_CONSLOCK(consLockCardinality)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
SCIP_DECL_CONSPRINT(consPrintCardinality)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
SCIP_DECL_CONSCOPY(consCopyCardinality)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
SCIP_DECL_CONSPARSE(consParseCardinality)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
3025 /* add variable */
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
SCIP_DECL_CONSGETVARS(consGetVarsCardinality)3056 SCIP_DECL_CONSGETVARS(consGetVarsCardinality)
3057 { /*lint --e{715}*/
3058 SCIP_CONSDATA* consdata;
3059
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
SCIP_DECL_CONSGETNVARS(consGetNVarsCardinality)3078 SCIP_DECL_CONSGETNVARS(consGetNVarsCardinality)
3079 { /*lint --e{715}*/
3080 SCIP_CONSDATA* consdata;
3081
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
SCIP_DECL_EVENTEXEC(eventExecCardinality)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 */
SCIPincludeConshdlrCardinality(SCIP * scip)3236 SCIP_RETCODE SCIPincludeConshdlrCardinality(
3237 SCIP* scip /**< SCIP data structure */
3238 )
3239 {
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 {
3253 SCIPerrorMessage("event handler for cardinality constraints not found.\n");
3254 return SCIP_PLUGINNOTFOUND;
3255 }
3256
3257 /* include constraint handler */
3258 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
3259 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
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,
3275 CONSHDLR_PROP_TIMING) );
3276 /*SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropCardinality) ); @todo: implement repropagation */
3277 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCardinality, consSepasolCardinality, CONSHDLR_SEPAFREQ,
3278 CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
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 */
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)3307 SCIP_RETCODE SCIPcreateConsCardinality(
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 {
3354 SCIPerrorMessage("<%s> constraint handler not found\n", CONSHDLR_NAME);
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) );
3427 SCIP_CALL( SCIPaddVar(scip, var) );
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 */
SCIPcreateConsBasicCardinality(SCIP * scip,SCIP_CONS ** cons,const char * name,int nvars,SCIP_VAR ** vars,int cardval,SCIP_VAR ** indvars,SCIP_Real * weights)3507 SCIP_RETCODE SCIPcreateConsBasicCardinality(
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) */
SCIPchgCardvalCardinality(SCIP * scip,SCIP_CONS * cons,int cardval)3528 SCIP_RETCODE SCIPchgCardvalCardinality(
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 */
SCIPaddVarCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_VAR * var,SCIP_VAR * indvar,SCIP_Real weight)3557 SCIP_RETCODE SCIPaddVarCardinality(
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 */
SCIPappendVarCardinality(SCIP * scip,SCIP_CONS * cons,SCIP_VAR * var,SCIP_VAR * indvar)3594 SCIP_RETCODE SCIPappendVarCardinality(
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 */
SCIPgetNVarsCardinality(SCIP * scip,SCIP_CONS * cons)3629 int SCIPgetNVarsCardinality(
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 */
SCIPgetVarsCardinality(SCIP * scip,SCIP_CONS * cons)3653 SCIP_VAR** SCIPgetVarsCardinality(
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) */
SCIPgetCardvalCardinality(SCIP * scip,SCIP_CONS * cons)3677 int SCIPgetCardvalCardinality(
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) */
SCIPgetWeightsCardinality(SCIP * scip,SCIP_CONS * cons)3700 SCIP_Real* SCIPgetWeightsCardinality(
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 }
3722