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