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