Scippy

SCIP

Solving Constraint Integer Programs

cons_cardinality.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (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 */
301 aggrconst = SCIPvarGetMultaggrConstant(var);
302 if( SCIPisZero(scip, aggrconst) )
303 {
304 SCIP_VAR** aggrvars;
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);
314 aggrvars = SCIPvarGetMultaggrVars(var);
315 aggrvals = SCIPvarGetMultaggrScalars(var);
316 for( i = 0; i < naggrvars; ++i )
317 {
318 if( (SCIPisPositive(scip, aggrvals[i]) && SCIPisNegative(scip, SCIPvarGetLbLocal(aggrvars[i]))) ||
319 (SCIPisNegative(scip, aggrvals[i]) && SCIPisPositive(scip, SCIPvarGetUbLocal(aggrvars[i]))) )
320 {
321 allnonnegative = FALSE;
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
406 newsize = SCIPcalcMemGrowSize(scip, num);
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 }
419 assert(num <= consdata->maxvars);
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 {
543 char varname[SCIP_MAXSTRLEN];
544 SCIP_VAR* newvar;
545
546 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(var));
547 SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE,
548 NULL, NULL, NULL, NULL, NULL) );
549 SCIP_CALL( SCIPaddVar(scip, newvar) );
550 indvar = newvar;
551
552 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
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 {
569 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
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 {
662 char varname[SCIP_MAXSTRLEN];
663 SCIP_VAR* newvar;
664
665 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(var));
666 SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE,
667 NULL, NULL, NULL, NULL, NULL) );
668 SCIP_CALL( SCIPaddVar(scip, newvar) );
669 indvar = newvar;
670
671 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
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 {
688 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
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 {
792 if( SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[j])) )
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);
870 assert(nremovedvars != 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;
883 allvarsbinary = TRUE;
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;
892 SCIP_VAR* oldvar;
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 */
946 lb = SCIPvarGetLbLocal(var);
947 ub = SCIPvarGetUbLocal(var);
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",
996 SCIPvarGetName(var), SCIPconsGetName(cons));
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) )
1028 allvarsbinary = FALSE;
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 */
1069 assert(!SCIPconsIsModifiable(cons));
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 {
1080 SCIP_CONS* knapsackcons;
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*/
1093 SCIP_CALL( SCIPaddCons(scip, knapsackcons) );
1094 SCIP_CALL( SCIPreleaseCons(scip, &knapsackcons) );
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 */
1101 assert(!SCIPconsIsModifiable(cons));
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);
1141 assert(nchgdomain != 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
1214 allvarfixed = FALSE;
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 {
1229 assert(!SCIPconsIsModifiable(cons));
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;
1240 SCIP_VAR** eventvars;
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 {
1272 SCIP_VAR* implvar;
1273
1274 implvar = eventdata->var;
1275
1276 /* fix implied variable to zero if not done already */
1277 if( SCIPisFeasNegative(scip, SCIPvarGetLbLocal(implvar)) ||
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",
1295 SCIPvarGetName(implvar), SCIPvarGetName(var));
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",
1331 SCIPvarGetName(indvar), SCIPvarGetName(var));
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 */
1363 assert(!SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[branchpos])));
1364 assert(SCIPisFeasZero(scip, SCIPvarGetLbLocal(indvars[branchpos])));
1365 assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(indvars[branchpos]), 1.0));
1366
1367 /* create branches */
1368 SCIPdebugMsg(scip, "apply unbalanced branching on variable <%s> of constraint <%s>.\n",
1369 SCIPvarGetName(indvars[branchpos]), SCIPconsGetName(branchcons));
1370
1371 /* create node 1 */
1372
1373 /* calculate node selection and objective estimate for node 1 */
1375 SCIPcalcChildEstimate(scip, vars[branchpos], 0.0) ) );
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 {
1405 objest += SCIPcalcChildEstimateIncrease(scip, vars[j], SCIPgetSolVal(scip, sol, vars[j]), 0.0);
1406 nodeselest += SCIPcalcNodeselPriority(scip, vars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1407#ifndef NDEBUG
1408 ++cnt;
1409#endif
1410 }
1411 }
1412 assert(objest >= SCIPgetLocalTransEstimate(scip));
1413 assert(cnt == nvars - (1 + branchnnonzero));
1414 assert(cnt > 0);
1415
1416 /* create node 2 */
1417 SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) );
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{
1464 SCIP_VAR** branchvars;
1465 SCIP_VAR** branchindvars;
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 */
1500 nbuffer = nvars-branchnnonzero;
1501 SCIP_CALL( SCIPallocBufferArray(scip, &branchvars, nbuffer) );
1502 SCIP_CALL( SCIPallocBufferArray(scip, &branchindvars, nbuffer) );
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 */
1512 if( SCIPvarGetLbLocal(indvars[j]) != 1.0 && !SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var))
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];
1523 branchvars[nbranchvars++] = var;
1524
1525 if( !SCIPisFeasZero(scip, val) )
1526 ++cnt;
1527 }
1528 else
1529 ++nzero;
1530 }
1531 else
1532 ++nnonzero;
1533 }
1534 assert(nnonzero == branchnnonzero);
1535 assert(nbranchvars <= nvars - branchnnonzero);
1536
1537 assert(cnt >= cardval-nnonzero);
1538 assert(!SCIPisFeasZero(scip, weight2));
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 {
1553 assert(SCIPisFeasPositive(scip, SCIPvarGetUbLocal(branchvars[j])));
1554 sum1 += val / SCIPvarGetUbLocal(branchvars[j]);
1555 }
1556 else if( SCIPisFeasNegative(scip, val) )
1557 {
1558 assert(SCIPisFeasNegative(scip, SCIPvarGetLbLocal(branchvars[j])));
1559 sum1 += val / SCIPvarGetLbLocal(branchvars[j]);
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 {
1570 assert(SCIPisFeasPositive(scip, SCIPvarGetUbLocal(branchvars[j])));
1571 sum2 += val/SCIPvarGetUbLocal(branchvars[j]);
1572 }
1573 else if( SCIPisFeasNegative(scip, val) )
1574 {
1575 assert(SCIPisFeasNegative(scip, SCIPvarGetLbLocal(branchvars[j])));
1576 sum2 += val/SCIPvarGetLbLocal(branchvars[j]);
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*/
1583 splitval1 = SCIPfloor(scip, splitval1/2);
1584 splitval1 = MAX(splitval1, 0);
1585 assert((int)splitval1 >= 0);
1586 assert((int)splitval1 <= MIN(newcardval-1, ind));
1587 splitval2 = (SCIP_Real)(newcardval-1);
1588 splitval2 -= splitval1;
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 {
1595 SCIP_CALL( branchUnbalancedCardinality(scip, sol, branchcons, vars, indvars, nvars, cardval,
1596 branchnnonzero, branchpos) );
1597 }
1598 else
1599 {
1600 char name[SCIP_MAXSTRLEN];
1601 SCIP_NODE* node1;
1602 SCIP_NODE* node2;
1603 SCIP_CONS* cons1;
1604 SCIP_CONS* cons2;
1605
1606 SCIPdebugMsg(scip, "apply balanced branching on constraint <%s>.\n", SCIPconsGetName(branchcons));
1607
1608 if( SCIPisFeasZero(scip, splitval1) )
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 {
1620 objest += SCIPcalcChildEstimateIncrease(scip, branchvars[j], SCIPgetSolVal(scip, sol, branchvars[j]), 0.0);
1621 nodeselest += SCIPcalcNodeselPriority(scip, branchvars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1622 }
1623 assert( objest >= SCIPgetLocalTransEstimate(scip) );
1624
1625 /* create node 1 */
1626 SCIP_CALL( SCIPcreateChild(scip, &node1, nodeselest, objest) );
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 */
1641 SCIP_CALL( SCIPcreateConsCardinality(scip, &cons1, name, ind+1, branchvars, (int)splitval1, branchindvars, NULL,
1643
1644 /* add constraint to node */
1645 SCIP_CALL( SCIPaddConsNode(scip, node1, cons1, NULL) );
1646
1647 /* release constraint */
1648 SCIP_CALL( SCIPreleaseCons(scip, &cons1) );
1649 }
1650
1651 if( SCIPisFeasZero(scip, splitval2) )
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 {
1663 objest += SCIPcalcChildEstimateIncrease(scip, branchvars[j], SCIPgetSolVal(scip, sol, branchvars[j]), 0.0);
1664 nodeselest += SCIPcalcNodeselPriority(scip, branchvars[j], SCIP_BRANCHDIR_DOWNWARDS, 0.0);
1665 }
1666 assert(nbranchvars - (ind + 1) > 0);
1667 assert(objest >= SCIPgetLocalTransEstimate(scip));
1668
1669 /* create node 1 */
1670 SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) );
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 */
1693 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "brright_#% " SCIP_LONGINT_FORMAT , SCIPgetNNodes(scip));
1694 SCIP_CALL( SCIPcreateConsCardinality(scip, &cons2, name, cnt, branchvars, (int)splitval2, branchindvars, NULL,
1696
1697 /* add constraint to node */
1698 SCIP_CALL( SCIPaddConsNode(scip, node2, cons2, NULL) );
1699
1700 /* release constraint */
1701 SCIP_CALL( SCIPreleaseCons(scip, &cons2) );
1702 }
1703 }
1704
1705 /* free buffer arrays */
1706 SCIPfreeBufferArray(scip, &branchindvars);
1707 SCIPfreeBufferArray(scip, &branchvars);
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;
1748 SCIP_CONS* branchcons;
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) );
1773 *result = SCIP_FEASIBLE;
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",
1816 SCIPconsGetName(cons), cutoff, nchgdomain);
1817 if( cutoff )
1818 {
1819 *result = SCIP_CUTOFF;
1820 return SCIP_OKAY;
1821 }
1822 if( nchgdomain > 0 )
1823 {
1824 *result = SCIP_REDUCEDDOM;
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 {
1845 *result = SCIP_CUTOFF;
1846 return SCIP_OKAY;
1847 }
1848
1849 assert(SCIPvarGetStatus(indvars[j]) != SCIP_VARSTATUS_MULTAGGR);
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);
1892 *result = SCIP_CUTOFF;
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
1919 *result = SCIP_REDUCEDDOM;
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;
1928 branchnnonzero = nnonzero;
1929 branchpos = pos;
1930 branchallneg = allneg;
1931 branchallpos = allpos;
1932 }
1933 }
1934
1935 /* if all constraints are feasible */
1936 if( branchcons == NULL )
1937 {
1938 SCIP_SOL* primsol;
1939 SCIP_Bool success;
1940
1941 /* polish primal solution */
1942 SCIP_CALL( SCIPcreateSolCopy(scip, &primsol, sol) );
1943 SCIP_CALL( polishPrimalSolution(scip, conss, nconss, sol, primsol) );
1944 SCIP_CALL( SCIPtrySol(scip, primsol, FALSE, TRUE, FALSE, TRUE, FALSE, &success) );
1945 SCIP_CALL( SCIPfreeSol(scip, &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 {
1973 SCIP_CALL( branchBalancedCardinality(scip, conshdlr, sol, branchcons, vars, indvars, nvars, cardval, branchnnonzero, branchpos,
1974 conshdlrdata->balancedcutoff) );
1975 }
1976 else
1977 {
1978 SCIP_CALL( branchUnbalancedCardinality(scip, sol, branchcons, vars, indvars, nvars, cardval, branchnnonzero,
1979 branchpos) );
1980 }
1981
1982 SCIP_CALL( SCIPresetConsAge(scip, branchcons) );
1983 *result = SCIP_BRANCHED;
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;
2034 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2035 SCIP_CALL( SCIPallocBufferArray(scip, &vals, 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);
2123 SCIPfreeBufferArray(scip, &vars);
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 {
2190 assert(SCIPisInfinity(scip, -SCIProwGetLhs(rowub)));
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 {
2207 assert(SCIPisInfinity(scip, -SCIProwGetLhs(rowlb)));
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
2262 *result = SCIP_DIDNOTRUN;
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
2271 *result = SCIP_DIDNOTFIND;
2272
2273 /* separate bound inequalities from cardinality constraints */
2274 SCIP_CALL( initsepaBoundInequalityFromCardinality(scip, conshdlr, conss, nconss, sol, TRUE, &ngen, &cutoff) );
2275 if( cutoff )
2276 {
2277 *result = SCIP_CUTOFF;
2278 return SCIP_OKAY;
2279 }
2280
2281 /* evaluate results */
2282 if( ngen > 0 )
2283 *result = SCIP_SEPARATED;
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
2293SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCardinality)
2294{ /*lint --e{715}*/
2295 assert(scip != NULL);
2296 assert(conshdlr != NULL);
2297 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
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
2309SCIP_DECL_CONSFREE(consFreeCardinality)
2310{
2311 SCIP_CONSHDLRDATA* conshdlrdata;
2312
2313 assert(scip != NULL);
2314 assert(conshdlr != NULL);
2315 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
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
2333SCIP_DECL_CONSEXITSOL(consExitsolCardinality)
2334{ /*lint --e{715}*/
2335 SCIP_CONSHDLRDATA* conshdlrdata;
2336 int c;
2337
2338 assert(scip != NULL);
2339 assert(conshdlr != NULL);
2340 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
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
2379SCIP_DECL_CONSDELETE(consDeleteCardinality)
2380{ /*lint --e{737, 647}*/
2381 assert(scip != NULL);
2382 assert(conshdlr != NULL);
2383 assert(cons != NULL);
2384 assert(consdata != NULL);
2385 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
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
2437SCIP_DECL_CONSTRANS(consTransCardinality)
2438{
2439 SCIP_CONSDATA* consdata;
2440 SCIP_CONSHDLRDATA* conshdlrdata;
2441 SCIP_CONSDATA* sourcedata;
2442 char s[SCIP_MAXSTRLEN];
2443 int j;
2444
2445 assert(scip != NULL);
2446 assert(conshdlr != NULL);
2447 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2448 assert(sourcecons != NULL);
2449 assert(targetcons != 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 */
2459 sourcedata = SCIPconsGetData(sourcecons);
2460 assert(sourcedata != NULL);
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 */
2503 (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons));
2504 SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
2505 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
2506 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
2507 SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
2508 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
2509 SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
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
2535SCIP_DECL_CONSPRESOL(consPresolCardinality)
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);
2546 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2547 assert(result != NULL);
2548
2549 SCIPdebugMsg(scip, "Presolving cardinality constraints.\n");
2550
2551 *result = SCIP_DIDNOTRUN;
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
2565 *result = SCIP_DIDNOTFIND;
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);
2583 assert(!SCIPconsIsModifiable(cons));
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");
2592 *result = SCIP_CUTOFF;
2593 return SCIP_OKAY;
2594 }
2595
2596 if( success )
2597 *result = SCIP_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
2611SCIP_DECL_CONSINITLP(consInitlpCardinality)
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
2627SCIP_DECL_CONSSEPALP(consSepalpCardinality)
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
2641SCIP_DECL_CONSSEPASOL(consSepasolCardinality)
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
2655SCIP_DECL_CONSENFOLP(consEnfolpCardinality)
2656{ /*lint --e{715}*/
2657 assert(scip != NULL);
2658 assert(conshdlr != NULL);
2659 assert(conss != NULL);
2660 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
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
2670SCIP_DECL_CONSENFORELAX(consEnforelaxCardinality)
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
2685SCIP_DECL_CONSENFOPS(consEnfopsCardinality)
2686{ /*lint --e{715}*/
2687 assert(scip != NULL);
2688 assert(conshdlr != NULL);
2689 assert(conss != NULL);
2690 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2691 assert(result != NULL);
2692
2693 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
2703SCIP_DECL_CONSCHECK(consCheckCardinality)
2704{ /*lint --e{715}*/
2705 int c;
2706
2707 assert(scip != NULL);
2708 assert(conshdlr != NULL);
2709 assert(conss != NULL);
2710 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
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]) );
2740 *result = SCIP_INFEASIBLE;
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 )
2761 SCIPupdateSolConsViolation(scip, sol, 1.0, 1.0);
2762 return SCIP_OKAY;
2763 }
2764 }
2765 }
2766 }
2767 *result = SCIP_FEASIBLE;
2768
2769 return SCIP_OKAY;
2770}
2771
2772/** domain propagation method of constraint handler */
2773static
2774SCIP_DECL_CONSPROP(consPropCardinality)
2775{ /*lint --e{715}*/
2776 int nchgdomain = 0;
2777 int c;
2778
2779 assert(scip != NULL);
2780 assert(conshdlr != NULL);
2781 assert(conss != NULL);
2782 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2783 assert(result != NULL);
2784 *result = SCIP_DIDNOTRUN;
2785
2786 assert(SCIPisTransformed(scip));
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
2795 *result = SCIP_DIDNOTFIND;
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
2802 *result = SCIP_DIDNOTFIND;
2803 SCIP_CALL( propCardinality(scip, cons, consdata, &cutoff, &nchgdomain) );
2804 if( cutoff )
2805 {
2806 *result = SCIP_CUTOFF;
2807 return SCIP_OKAY;
2808 }
2809 }
2810 SCIPdebugMsg(scip, "Propagated %d domains.\n", nchgdomain);
2811 if( nchgdomain > 0 )
2812 *result = SCIP_REDUCEDDOM;
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
2830SCIP_DECL_CONSLOCK(consLockCardinality)
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);
2841 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2842 assert(locktype == SCIP_LOCKTYPE_MODEL);
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
2882SCIP_DECL_CONSPRINT(consPrintCardinality)
2883{ /*lint --e{715}*/
2884 SCIP_CONSDATA* consdata;
2885 int j;
2886
2887 assert(scip != NULL);
2888 assert(conshdlr != NULL);
2889 assert(cons != NULL);
2890 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
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
2912SCIP_DECL_CONSCOPY(consCopyCardinality)
2913{ /*lint --e{715}*/
2914 SCIP_CONSDATA* sourceconsdata;
2915 SCIP_VAR** sourcevars;
2916 SCIP_VAR** targetvars;
2917 SCIP_VAR** sourceindvars;
2918 SCIP_VAR** targetindvars;
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);
2927 assert(sourcecons != NULL);
2928 assert(SCIPisTransformed(sourcescip));
2929 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(sourcecons)), CONSHDLR_NAME) == 0);
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
2940 sourceconsdata = SCIPconsGetData(sourcecons);
2941 assert(sourceconsdata != NULL);
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;
2950 assert(sourcevars != NULL);
2951 sourceindvars = sourceconsdata->indvars;
2952 assert(sourceindvars != NULL);
2953 sourceweights = sourceconsdata->weights;
2954 assert(sourceweights != NULL);
2955
2956 /* duplicate variable array */
2957 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetvars, nvars) );
2958 SCIP_CALL( SCIPallocBufferArray(sourcescip, &targetindvars, nvars) );
2959 SCIP_CALL( SCIPduplicateBufferArray(sourcescip, &targetweights, sourceweights, nvars) );
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 {
2977 SCIP_CALL( SCIPcreateConsCardinality(scip, cons, consname, nvars, targetvars, sourceconsdata->cardval, targetindvars,
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
2991SCIP_DECL_CONSPARSE(consParseCardinality)
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
3107SCIP_DECL_CONSGETVARS(consGetVarsCardinality)
3108{ /*lint --e{715}*/
3109 SCIP_CONSDATA* consdata;
3110
3111 consdata = SCIPconsGetData(cons);
3112 assert(consdata != NULL);
3113
3114 if( varssize < consdata->nvars )
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
3129SCIP_DECL_CONSGETNVARS(consGetNVarsCardinality)
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
3144SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphCardinality)
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 */
3167 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, -SCIPinfinity(scip), rhs, &consnodeidx) );
3168
3169 /* create nodes and edges for each variable */
3170 nvars = SCIPgetNVars(scip);
3171 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3172 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
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 */
3177 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_CARD_TUPLE , &pairnodeidx) );
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 */
3196 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
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 {
3203 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]);
3204
3205 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
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 */
3225 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
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 {
3232 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]);
3233
3234 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
3235 }
3236 }
3237
3238 SCIPfreeBufferArray(scip, &vals);
3239 SCIPfreeBufferArray(scip, &vars);
3240
3241 assert(success != NULL);
3242 *success = TRUE;
3243
3244 return SCIP_OKAY;
3245}
3246
3247/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
3248static
3249SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphCardinality)
3250{ /*lint --e{715}*/
3251 SCIP_CONSDATA* consdata;
3252 SCIP_VAR** vars;
3253 SCIP_Real* vals;
3254 SCIP_Real constant;
3255 SCIP_Real rhs;
3256 int consnodeidx;
3257 int pairnodeidx;
3258 int nodeidx;
3259 int nconsvars;
3260 int nlocvars;
3261 int nvars;
3262 int i;
3263
3264 consdata = SCIPconsGetData(cons);
3265 assert(consdata != NULL);
3266 assert(graph != NULL);
3267
3268 nconsvars = consdata->nvars;
3269 rhs = (SCIP_Real) consdata->cardval;
3270
3271 /* add node for constraint */
3272 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, -SCIPinfinity(scip), rhs, &consnodeidx) );
3273
3274 /* create nodes and edges for each variable */
3275 nvars = SCIPgetNVars(scip);
3276 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3277 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
3278
3279 for( i = 0; i < nconsvars; ++i )
3280 {
3281 /* connect each variable and its indicator variable with an intermediate node, which is connected with consnode */
3282 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_CARD_TUPLE , &pairnodeidx) );
3283
3284 vars[0] = consdata->vars[i];
3285 vals[0] = 1.0;
3286 nlocvars = 1;
3287 constant = 0.0;
3288
3289 /* use SYM_SYMTYPE_PERM here to NOT center variable domains at 0, as the latter might not preserve
3290 * cardinality constraints */
3292 &nlocvars, &constant, SCIPisTransformed(scip)) );
3293
3294 /* check whether variable is (multi-) aggregated or negated */
3295 if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) )
3296 {
3297 int sumnodeidx;
3298 int j;
3299
3300 /* encode aggregation by a sum-expression */
3301 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &sumnodeidx) ); /*lint !e641*/
3302
3303 /* we do not need to take weights of variables into account;
3304 * they are only used to sort variables within the constraint */
3305 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, sumnodeidx, FALSE, 0.0) );
3306
3307 /* add nodes and edges for variables in aggregation, do not add edges to negated variables
3308 * since this might not necessarily be a symmetry of the cardinality constraint; therefore,
3309 * do not use SCIPaddSymgraphVarAggregation() */
3310 for( j = 0; j < nlocvars; ++j )
3311 {
3312 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[j]);
3313 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, TRUE, vals[j]) );
3314 }
3315
3316 /* possibly add node for constant */
3317 if( ! SCIPisZero(scip, constant) )
3318 {
3319 SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, constant, &nodeidx) );
3320
3321 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, sumnodeidx, nodeidx, FALSE, 0.0) );
3322 }
3323 }
3324 else if( nlocvars == 1 )
3325 {
3326 SCIP_Bool allownegation = FALSE;
3327
3328 /* a negation is allowed if it is centered around 0 */
3331 || SCIPisZero(scip, (SCIPvarGetLbGlobal(vars[0]) + SCIPvarGetUbGlobal(vars[0]))/2)) )
3332 allownegation = TRUE;
3333
3334 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]);
3335 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, TRUE, 1.0) );
3336
3337 nodeidx = SCIPgetSymgraphNegatedVarnodeidx(scip, graph, vars[0]);
3338 if( allownegation )
3339 {
3340 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, TRUE, 1.0) );
3341 }
3342 else
3343 {
3344 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
3345 }
3346 }
3347
3348 /* connect indicator variable with pair node, do not add edges to negated variables since negating
3349 * might not preserve the cardinality requirement
3350 */
3351 vars[0] = consdata->indvars[i];
3352 vals[0] = 1.0;
3353 nlocvars = 1;
3354 constant = 0.0;
3355
3357 &nlocvars, &constant, SCIPisTransformed(scip)) );
3358
3359 /* check whether variable is (multi-)aggregated or negated */
3360 if( nlocvars > 1 || !SCIPisEQ(scip, vals[0], 1.0) || !SCIPisZero(scip, constant) )
3361 {
3362 /* encode aggregation by a sum-expression */
3363 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/
3364
3365 /* we do not need to take weights of variables into account;
3366 * they are only used to sort variables within the constraint */
3367 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
3368
3369 /* add nodes and edges for variables in aggregation */
3370 SCIP_CALL( SCIPaddSymgraphVarAggregation(scip, graph, nodeidx, vars, vals, nlocvars, constant) );
3371 }
3372 else if( nlocvars == 1 )
3373 {
3374 nodeidx = SCIPgetSymgraphVarnodeidx(scip, graph, vars[0]);
3375
3376 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, pairnodeidx, nodeidx, FALSE, 0.0) );
3377 }
3378 }
3379
3380 SCIPfreeBufferArray(scip, &vals);
3381 SCIPfreeBufferArray(scip, &vars);
3382
3383 assert(success != NULL);
3384 *success = TRUE;
3385
3386 return SCIP_OKAY;
3387}
3388
3389/* ---------------- Callback methods of event handler ---------------- */
3390
3391/* exec the event handler
3392 *
3393 * update the number of variables fixed to be nonzero
3394 * update the bound constraints
3395 */
3396static
3397SCIP_DECL_EVENTEXEC(eventExecCardinality)
3398{
3399 SCIP_EVENTTYPE eventtype;
3400 SCIP_CONSDATA* consdata;
3401 SCIP_Real oldbound;
3402 SCIP_Real newbound;
3403 SCIP_VAR* var;
3404
3405 assert(eventhdlr != NULL);
3406 assert(eventdata != NULL);
3407 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3408 assert(event != NULL);
3409
3410 consdata = eventdata->consdata;
3411 assert(consdata != NULL);
3412 assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3413 assert(consdata->eventdatascurrent != NULL);
3414 assert(consdata->eventvarscurrent != NULL);
3415
3416 var = SCIPeventGetVar(event);
3417 assert(var != NULL);
3418 oldbound = SCIPeventGetOldbound(event);
3419 newbound = SCIPeventGetNewbound(event);
3420 eventtype = SCIPeventGetType(event);
3421
3422#ifdef SCIP_DEBUG
3423 if( ( eventdata->varmarked && var == eventdata->var) || ( eventdata->indvarmarked && var == eventdata->indvar) )
3424 {
3425 int i;
3426
3427 for( i = 0; i < consdata->neventdatascurrent; ++i )
3428 {
3429 if( var == consdata->eventvarscurrent[i] )
3430 {
3431 break;
3432 }
3433 }
3434 assert(i < consdata->neventdatascurrent);
3435 }
3436#endif
3437
3438 if( eventtype & SCIP_EVENTTYPE_GBDCHANGED )
3439 {
3440 if( eventtype == SCIP_EVENTTYPE_GLBCHANGED )
3441 {
3442 /* global lower bound is not negative anymore -> remove down lock */
3443 if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) )
3444 SCIP_CALL( SCIPunlockVarCons(scip, var, consdata->cons, TRUE, FALSE) );
3445 /* global lower bound turned negative -> add down lock */
3446 else if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
3447 SCIP_CALL( SCIPlockVarCons(scip, var, consdata->cons, TRUE, FALSE) );
3448
3449 return SCIP_OKAY;
3450 }
3451 if( eventtype == SCIP_EVENTTYPE_GUBCHANGED )
3452 {
3453 /* global upper bound is not positive anymore -> remove up lock */
3454 if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) )
3455 SCIP_CALL( SCIPunlockVarCons(scip, var, consdata->cons, FALSE, TRUE) );
3456 /* global upper bound turned positive -> add up lock */
3457 else if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
3458 SCIP_CALL( SCIPlockVarCons(scip, var, consdata->cons, FALSE, TRUE) );
3459
3460 return SCIP_OKAY;
3461 }
3462 }
3463
3464 /* if variable is an indicator variable */
3465 if( var == eventdata->indvar )
3466 {
3467 assert(SCIPvarIsBinary(var));
3468 assert(consdata->cons != NULL);
3469
3470 if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED )
3471 ++(consdata->ntreatnonzeros);
3472 else if( eventtype == SCIP_EVENTTYPE_LBRELAXED )
3473 --(consdata->ntreatnonzeros);
3474 else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED && ! eventdata->indvarmarked )
3475 {
3476 assert(oldbound == 1.0 && newbound == 0.0 );
3477
3478 /* save event data for propagation */
3479 consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3480 consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3481 ++consdata->neventdatascurrent;
3482 eventdata->indvarmarked = TRUE;
3483 assert(consdata->neventdatascurrent <= 4 * consdata->maxvars);
3484 assert(var == eventdata->indvar );
3485 }
3486 assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3487 }
3488
3489 /* if variable is an implied variable,
3490 * notice that the case consdata->var = consdata->indvar is possible */
3491 if( var == eventdata->var && ! eventdata->varmarked )
3492 {
3493 if( eventtype == SCIP_EVENTTYPE_LBTIGHTENED )
3494 {
3495 /* if variable is now fixed to be nonzero */
3496 if( !SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
3497 {
3498 /* save event data for propagation */
3499 consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3500 consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3501 ++consdata->neventdatascurrent;
3502 eventdata->varmarked = TRUE;
3503 assert(consdata->neventdatascurrent <= 4 * consdata->maxvars );
3504 assert(var == eventdata->var );
3505 }
3506 }
3507 else if( eventtype == SCIP_EVENTTYPE_UBTIGHTENED )
3508 {
3509 /* if variable is now fixed to be nonzero */
3510 if( !SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
3511 {
3512 /* save event data for propagation */
3513 consdata->eventdatascurrent[consdata->neventdatascurrent] = eventdata;
3514 consdata->eventvarscurrent[consdata->neventdatascurrent] = var;
3515 ++consdata->neventdatascurrent;
3516 eventdata->varmarked = TRUE;
3517 assert(consdata->neventdatascurrent <= 4 * consdata->maxvars );
3518 assert(var == eventdata->var);
3519 }
3520 }
3521 }
3522 assert(0 <= consdata->ntreatnonzeros && consdata->ntreatnonzeros <= consdata->nvars);
3523
3524 SCIPdebugMsg(scip, "event exec cons <%s>: changed bound of variable <%s> from %f to %f (ntreatnonzeros: %d).\n",
3525 SCIPconsGetName(consdata->cons), SCIPvarGetName(SCIPeventGetVar(event)),
3526 oldbound, newbound, consdata->ntreatnonzeros);
3527
3528 return SCIP_OKAY;
3529}
3530
3531/* ---------------- Constraint specific interface methods ---------------- */
3532
3533/** creates the handler for cardinality constraints and includes it in SCIP */
3535 SCIP* scip /**< SCIP data structure */
3536 )
3537{
3538 SCIP_CONSHDLRDATA* conshdlrdata;
3539 SCIP_CONSHDLR* conshdlr;
3540
3541 /* create constraint handler data */
3542 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3543 conshdlrdata->eventhdlr = NULL;
3544 conshdlrdata->varhash = NULL;
3545
3546 /* create event handler for bound change events */
3548 eventExecCardinality, NULL) );
3549 if( conshdlrdata->eventhdlr == NULL )
3550 {
3551 SCIPerrorMessage("event handler for cardinality constraints not found.\n");
3552 return SCIP_PLUGINNOTFOUND;
3553 }
3554
3555 /* include constraint handler */
3558 consEnfolpCardinality, consEnfopsCardinality, consCheckCardinality, consLockCardinality, conshdlrdata) );
3559 assert(conshdlr != NULL);
3560
3561 /* set non-fundamental callbacks via specific setter functions */
3562 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyCardinality, consCopyCardinality) );
3563 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteCardinality) );
3564 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolCardinality) );
3565 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeCardinality) );
3566 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsCardinality) );
3567 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsCardinality) );
3568 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpCardinality) );
3569 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseCardinality) );
3571 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintCardinality) );
3572 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropCardinality, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3574 /*SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropCardinality) ); @todo: implement repropagation */
3575 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpCardinality, consSepasolCardinality, CONSHDLR_SEPAFREQ,
3577 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransCardinality) );
3578 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxCardinality) );
3579 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphCardinality) );
3580 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphCardinality) );
3581
3582 /* add cardinality constraint handler parameters */
3583 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/branchbalanced",
3584 "whether to use balanced instead of unbalanced branching",
3585 &conshdlrdata->branchbalanced, TRUE, DEFAULT_BRANCHBALANCED, NULL, NULL) );
3586
3587 SCIP_CALL( SCIPaddIntParam(scip, "constraints/" CONSHDLR_NAME "/balanceddepth",
3588 "maximum depth for using balanced branching (-1: no limit)",
3589 &conshdlrdata->balanceddepth, TRUE, DEFAULT_BALANCEDDEPTH, -1, INT_MAX, NULL, NULL) );
3590
3591 SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/balancedcutoff",
3592 "determines that balanced branching is only used if the branching cut off value "
3593 "w.r.t. the current LP solution is greater than a given value",
3594 &conshdlrdata->balancedcutoff, TRUE, DEFAULT_BALANCEDCUTOFF, 0.01, SCIP_REAL_MAX, NULL, NULL) );
3595
3596 return SCIP_OKAY;
3597}
3598
3599/** creates and captures a cardinality constraint
3600 *
3601 * We set the constraint to not be modifable. If the weights are non
3602 * NULL, the variables are ordered according to these weights (in
3603 * ascending order).
3604 *
3605 * @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons()
3606 */
3608 SCIP* scip, /**< SCIP data structure */
3609 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3610 const char* name, /**< name of constraint */
3611 int nvars, /**< number of variables in the constraint */
3612 SCIP_VAR** vars, /**< array with variables of constraint entries */
3613 int cardval, /**< number of variables allowed to be nonzero */
3614 SCIP_VAR** indvars, /**< indicator variables indicating which variables may be treated as nonzero
3615 * in cardinality constraint, or NULL if new indicator variables should be
3616 * introduced automatically */
3617 SCIP_Real* weights, /**< weights determining the variable order, or NULL if variables should be
3618 * ordered in the same way they were added to the constraint */
3619 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3620 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3621 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3622 * Usually set to TRUE. */
3623 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3624 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3625 SCIP_Bool check, /**< should the constraint be checked for feasibility?
3626 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3627 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3628 * Usually set to TRUE. */
3629 SCIP_Bool local, /**< is constraint only valid locally?
3630 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3631 SCIP_Bool dynamic, /**< is constraint subject to aging?
3632 * Usually set to FALSE. Set to TRUE for own cuts which
3633 * are separated as constraints. */
3634 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3635 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3636 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3637 * if it may be moved to a more global node?
3638 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3639 )
3640{
3641 SCIP_CONSHDLRDATA* conshdlrdata;
3642 SCIP_CONSHDLR* conshdlr;
3643 SCIP_CONSDATA* consdata;
3644 SCIP_Bool modifiable;
3645 SCIP_Bool transformed;
3646 int v;
3647
3648 modifiable = FALSE;
3649
3650 /* find the cardinality constraint handler */
3651 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3652 if( conshdlr == NULL )
3653 {
3654 SCIPerrorMessage("<%s> constraint handler not found\n", CONSHDLR_NAME);
3655 return SCIP_PLUGINNOTFOUND;
3656 }
3657
3658 /* get constraint handler data */
3659 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3660 assert(conshdlrdata != NULL);
3661
3662 /* are we in the transformed problem? */
3663 transformed = SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED;
3664
3665 /* create constraint data */
3666 SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
3667 consdata->cons = NULL;
3668 consdata->vars = NULL;
3669 consdata->indvars = NULL;
3670 consdata->eventdatas = NULL;
3671 consdata->nvars = nvars;
3672 consdata->cardval = cardval;
3673 consdata->maxvars = nvars;
3674 consdata->rowub = NULL;
3675 consdata->rowlb = NULL;
3676 consdata->eventdatascurrent = NULL;
3677 consdata->eventvarscurrent = NULL;
3678 consdata->neventdatascurrent = 0;
3679 consdata->ntreatnonzeros = transformed ? 0 : -1;
3680 consdata->weights = NULL;
3681
3682 if( nvars > 0 )
3683 {
3684 /* duplicate memory for implied variables */
3685 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->vars, vars, nvars) );
3686
3687 /* create indicator variables if not present */
3688 if( indvars != NULL )
3689 {
3690 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->indvars, indvars, nvars) );
3691 }
3692 else
3693 {
3694 if( conshdlrdata->varhash == NULL )
3695 {
3696 /* set up hash map */
3697 SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNTotalVars(scip)) );
3698 }
3699
3700 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->indvars, nvars) );
3701 for( v = 0; v < nvars; ++v )
3702 {
3703 SCIP_VAR* implvar;
3704
3705 implvar = vars[v];
3706 assert(implvar != NULL);
3707
3708 /* check whether an indicator variable already exists for implied variable */
3709 if( SCIPhashmapExists(conshdlrdata->varhash, implvar) )
3710 {
3711 assert((SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar) != NULL);
3712 consdata->indvars[v] = (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar);
3713 }
3714 else
3715 {
3716 /* if implied variable is binary, then it is not necessary to create an indicator variable */
3717 if( SCIPvarIsBinary(implvar) )
3718 consdata->indvars[v] = implvar;
3719 else
3720 {
3721 char varname[SCIP_MAXSTRLEN];
3722 SCIP_VAR* var;
3723
3724 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "ind_%s", SCIPvarGetName(vars[v]));
3725 SCIP_CALL( SCIPcreateVar(scip, &var, varname, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY, FALSE, FALSE,
3726 NULL, NULL, NULL, NULL, NULL) );
3727 SCIP_CALL( SCIPaddVar(scip, var) );
3728 consdata->indvars[v] = var;
3729 SCIP_CALL( SCIPreleaseVar(scip, &var) );
3730 }
3731
3732 /* insert implied variable to hash map */
3733 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, implvar, (void*) consdata->indvars[v]) );/*lint !e571*/
3734 assert(consdata->indvars[v] == (SCIP_VAR*) SCIPhashmapGetImage(conshdlrdata->varhash, implvar));
3735 assert(SCIPhashmapExists(conshdlrdata->varhash, implvar));
3736 }
3737 }
3738 }
3739
3740 /* allocate block memory */
3741 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatascurrent, 4*nvars) );/*lint !e647*/
3742 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventvarscurrent, 4*nvars) );/*lint !e647*/
3743 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->eventdatas, nvars) );
3744
3745 /* check weights */
3746 if( weights != NULL )
3747 {
3748 int* dummy;
3749
3750 /* store weights */
3751 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->weights, weights, nvars) );
3752
3753 /* create dummy array to make code compatible with SCIP 3.2.0
3754 * (the function SCIPsortRealPtrPtr() is not available) */
3755 SCIP_CALL( SCIPallocBufferArray(scip, &dummy, nvars) );
3756 for( v = 0; v < nvars; ++v )
3757 dummy[v] = 0;
3758
3759 /* sort variables - ascending order */
3760 SCIPsortRealPtrPtrInt(consdata->weights, (void**)consdata->vars, (void**)consdata->indvars, dummy, nvars);
3761
3762 SCIPfreeBufferArray(scip, &dummy);
3763 }
3764 }
3765 else
3766 {
3767 assert(weights == NULL);
3768 }
3769
3770 /* create cardinality constraint */
3771 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3772 local, modifiable, dynamic, removable, stickingatnode) );
3773
3774 consdata->cons = *cons;
3775 assert(consdata->cons != NULL);
3776
3777 /* replace original variables by transformed variables in transformed constraint, add locks, and catch events */
3778 for( v = nvars - 1; v >= 0; --v )
3779 {
3780 /* always use transformed variables in transformed constraints */
3781 if( transformed )
3782 {
3783 SCIP_CALL( SCIPgetTransformedVar(scip, consdata->vars[v], &(consdata->vars[v])) );
3784 SCIP_CALL( SCIPgetTransformedVar(scip, consdata->indvars[v], &(consdata->indvars[v])) );
3785 }
3786 assert(consdata->vars[v] != NULL);
3787 assert(consdata->indvars[v] != NULL);
3788 assert(transformed == SCIPvarIsTransformed(consdata->vars[v]));
3789 assert(transformed == SCIPvarIsTransformed(consdata->indvars[v]));
3790
3791 /* handle the new variable */
3792 SCIP_CALL( handleNewVariableCardinality(scip, *cons, consdata, conshdlrdata, consdata->vars[v],
3793 consdata->indvars[v], v, transformed, &consdata->eventdatas[v]) );
3794 assert(! transformed || consdata->eventdatas[v] != NULL);
3795 }
3796
3797 return SCIP_OKAY;
3798}
3799
3800/** creates and captures a cardinality constraint with all constraint flags set to their default values.
3801 *
3802 * @warning Do NOT set the constraint to be modifiable manually, because this might lead
3803 * to wrong results as the variable array will not be resorted
3804 *
3805 * @note the constraint gets captured, hence at one point you have to release it using the method \ref SCIPreleaseCons()
3806 */
3808 SCIP* scip, /**< SCIP data structure */
3809 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3810 const char* name, /**< name of constraint */
3811 int nvars, /**< number of variables in the constraint */
3812 SCIP_VAR** vars, /**< array with variables of constraint entries */
3813 int cardval, /**< number of variables allowed to be nonzero */
3814 SCIP_VAR** indvars, /**< indicator variables indicating which variables may be treated as nonzero
3815 * in cardinality constraint, or NULL if new indicator variables should be
3816 * introduced automatically */
3817 SCIP_Real* weights /**< weights determining the variable order, or NULL if variables should be
3818 * ordered in the same way they were added to the constraint */
3819 )
3820{
3821 SCIP_CALL( SCIPcreateConsCardinality(scip, cons, name, nvars, vars, cardval, indvars, weights, TRUE, TRUE, TRUE, TRUE,
3822 TRUE, FALSE, FALSE, FALSE, FALSE) );
3823
3824 return SCIP_OKAY;
3825}
3826
3827/** changes cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */
3829 SCIP* scip, /**< SCIP data structure */
3830 SCIP_CONS* cons, /**< pointer to hold the created constraint */
3831 int cardval /**< number of variables allowed to be nonzero */
3832 )
3833{
3834 SCIP_CONSDATA* consdata;
3835
3836 assert(scip != NULL);
3837 assert(cons != NULL);
3838
3839 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3840 {
3841 SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3842 return SCIP_INVALIDDATA;
3843 }
3844
3845 consdata = SCIPconsGetData(cons);
3846 assert(consdata != NULL);
3847
3848 SCIPdebugMsg(scip, "modify right hand side of cardinality constraint from <%i> to <%i>\n", consdata->cardval, cardval);
3849
3850 /* create constraint data */
3851 consdata->cardval = cardval;
3852
3853 return SCIP_OKAY;
3854}
3855
3856/** adds variable to cardinality constraint, the position is determined by the given weight */
3858 SCIP* scip, /**< SCIP data structure */
3859 SCIP_CONS* cons, /**< constraint */
3860 SCIP_VAR* var, /**< variable to add to the constraint */
3861 SCIP_VAR* indvar, /**< indicator variable indicating whether variable may be treated as nonzero
3862 * in cardinality constraint (or NULL if this variable should be created
3863 * automatically) */
3864 SCIP_Real weight /**< weight determining position of variable */
3865 )
3866{
3867 SCIP_CONSHDLRDATA* conshdlrdata;
3868 SCIP_CONSHDLR* conshdlr;
3869
3870 assert(scip != NULL);
3871 assert(var != NULL);
3872 assert(cons != NULL);
3873
3874 SCIPdebugMsg(scip, "adding variable <%s> to constraint <%s> with weight %g\n", SCIPvarGetName(var),
3875 SCIPconsGetName(cons), weight);
3876
3877 conshdlr = SCIPconsGetHdlr(cons);
3878 assert(conshdlr != NULL);
3879 if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 )
3880 {
3881 SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3882 return SCIP_INVALIDDATA;
3883 }
3884
3885 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3886 assert(conshdlrdata != NULL);
3887
3888 SCIP_CALL( addVarCardinality(scip, cons, conshdlrdata, var, indvar, weight) );
3889
3890 return SCIP_OKAY;
3891}
3892
3893/** appends variable to cardinality constraint */
3895 SCIP* scip, /**< SCIP data structure */
3896 SCIP_CONS* cons, /**< constraint */
3897 SCIP_VAR* var, /**< variable to add to the constraint */
3898 SCIP_VAR* indvar /**< indicator variable indicating whether variable may be treated as nonzero
3899 * in cardinality constraint (or NULL if this variable should be created
3900 * automatically) */
3901 )
3902{
3903 SCIP_CONSHDLRDATA* conshdlrdata;
3904 SCIP_CONSHDLR* conshdlr;
3905
3906 assert(scip != NULL);
3907 assert(var != NULL);
3908 assert(cons != NULL);
3909
3910 SCIPdebugMsg(scip, "appending variable <%s> to constraint <%s>\n", SCIPvarGetName(var), SCIPconsGetName(cons));
3911
3912 conshdlr = SCIPconsGetHdlr(cons);
3913 assert(conshdlr != NULL);
3914 if( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) != 0 )
3915 {
3916 SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3917 return SCIP_INVALIDDATA;
3918 }
3919
3920 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3921 assert(conshdlrdata != NULL);
3922
3923 SCIP_CALL( appendVarCardinality(scip, cons, conshdlrdata, var, indvar) );
3924
3925 return SCIP_OKAY;
3926}
3927
3928/** gets number of variables in cardinality constraint */
3930 SCIP* scip, /**< SCIP data structure */
3931 SCIP_CONS* cons /**< constraint */
3932 )
3933{
3934 SCIP_CONSDATA* consdata;
3935
3936 assert(scip != NULL);
3937 assert(cons != NULL);
3938
3939 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3940 {
3941 SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3942 SCIPABORT();
3943 return -1; /*lint !e527*/
3944 }
3945
3946 consdata = SCIPconsGetData(cons);
3947 assert(consdata != NULL);
3948
3949 return consdata->nvars;
3950}
3951
3952/** gets array of variables in cardinality constraint */
3954 SCIP* scip, /**< SCIP data structure */
3955 SCIP_CONS* cons /**< constraint data */
3956 )
3957{
3958 SCIP_CONSDATA* consdata;
3959
3960 assert(scip != NULL);
3961 assert(cons != NULL);
3962
3963 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3964 {
3965 SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3966 SCIPABORT();
3967 return NULL; /*lint !e527*/
3968 }
3969
3970 consdata = SCIPconsGetData(cons);
3971 assert(consdata != NULL);
3972
3973 return consdata->vars;
3974}
3975
3976/** gets cardinality value of cardinality constraint (i.e., right hand side of cardinality constraint) */
3978 SCIP* scip, /**< SCIP data structure */
3979 SCIP_CONS* cons /**< constraint data */
3980 )
3981{
3982 SCIP_CONSDATA* consdata;
3983
3984 assert(scip != NULL);
3985 assert(cons != NULL);
3986
3987 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3988 {
3989 SCIPerrorMessage("constraint is not a cardinality constraint.\n");
3990 return -1; /*lint !e527*/
3991 }
3992
3993 consdata = SCIPconsGetData(cons);
3994 assert(consdata != NULL);
3995
3996 return consdata->cardval;
3997}
3998
3999/** gets array of weights in cardinality constraint (or NULL if not existent) */
4001 SCIP* scip, /**< SCIP data structure */
4002 SCIP_CONS* cons /**< constraint data */
4003 )
4004{
4005 SCIP_CONSDATA* consdata;
4006
4007 assert(scip != NULL);
4008 assert(cons != NULL);
4009
4010 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
4011 {
4012 SCIPerrorMessage("constraint is not a cardinality constraint.\n");
4013 SCIPABORT();
4014 return NULL; /*lint !e527*/
4015 }
4016
4017 consdata = SCIPconsGetData(cons);
4018 assert(consdata != NULL);
4019
4020 return consdata->weights;
4021}
SCIP_VAR * w
Definition: circlepacking.c:67
static SCIP_RETCODE unlockVariableCardinality(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_VAR *indvar)
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
static SCIP_DECL_CONSFREE(consFreeCardinality)
static SCIP_DECL_CONSPARSE(consParseCardinality)
#define CONSHDLR_CHECKPRIORITY
static SCIP_DECL_CONSSEPALP(consSepalpCardinality)
#define CONSHDLR_DESC
static SCIP_DECL_CONSINITLP(consInitlpCardinality)
#define CONSHDLR_PROP_TIMING
static SCIP_RETCODE consdataEnsurevarsSizeCardinality(SCIP *scip, SCIP_CONSDATA *consdata, int num, SCIP_Bool reserveweights)
#define CONSHDLR_MAXPREROUNDS
static SCIP_DECL_CONSSEPASOL(consSepasolCardinality)
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_DECL_CONSEXITSOL(consExitsolCardinality)
static SCIP_RETCODE fixVariableZeroNode(SCIP *scip, SCIP_VAR *var, SCIP_NODE *node, SCIP_Bool *infeasible)
static SCIP_DECL_CONSPRESOL(consPresolCardinality)
static SCIP_DECL_CONSPRINT(consPrintCardinality)
static SCIP_RETCODE generateRowCardinality(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_Bool local, SCIP_ROW **rowlb, SCIP_ROW **rowub)
static SCIP_DECL_CONSDELETE(consDeleteCardinality)
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_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphCardinality)
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)
static SCIP_DECL_CONSCOPY(consCopyCardinality)
static SCIP_DECL_CONSCHECK(consCheckCardinality)
static SCIP_DECL_CONSENFOPS(consEnfopsCardinality)
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphCardinality)
#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_DECL_CONSTRANS(consTransCardinality)
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
static SCIP_DECL_CONSPROP(consPropCardinality)
static SCIP_DECL_CONSLOCK(consLockCardinality)
#define DEFAULT_BRANCHBALANCED
static SCIP_DECL_CONSENFORELAX(consEnforelaxCardinality)
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_DECL_CONSGETVARS(consGetVarsCardinality)
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
static SCIP_DECL_CONSGETNVARS(consGetNVarsCardinality)
#define CONSHDLR_DELAYSEPA
#define CONSHDLR_NAME
static SCIP_DECL_CONSENFOLP(consEnfolpCardinality)
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)
static SCIP_DECL_EVENTEXEC(eventExecCardinality)
#define CONSHDLR_DELAYPROP
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyCardinality)
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_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_Bool
Definition: def.h:91
#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)
Definition: scip_general.c:596
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
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,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
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)
Definition: scip_branch.c:920
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:947
SCIP_Real SCIPcalcChildEstimateIncrease(SCIP *scip, SCIP_VAR *var, SCIP_Real varsol, SCIP_Real targetvalue)
Definition: scip_branch.c:971
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1017
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
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 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 SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETPERMSYMGRAPH((*consgetpermsymgraph)))
Definition: scip_cons.c:900
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH((*consgetsignedpermsymgraph)))
Definition: scip_cons.c:924
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
int SCIPconshdlrGetSepaFreq(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:5130
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
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
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
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:4351
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:4676
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:4890
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:533
SCIP_RETCODE SCIPgetProbvarSum(SCIP *scip, SCIP_VAR **var, SCIP_Real *scalar, SCIP_Real *constant)
Definition: scip_var.c:1794
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4437
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPflattenVarAggregationGraph(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1693
SCIP_VAR ** SCIPvarGetMultaggrVars(SCIP_VAR *var)
Definition: var.c: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:8715
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4846
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:230
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1439
SCIP_Real * SCIPvarGetMultaggrScalars(SCIP_VAR *var)
Definition: var.c: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
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
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
#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_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
Definition: type_history.h:43
@ 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
Definition: type_retcode.h:52
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_PARAMETERWRONGVAL
Definition: type_retcode.h:57
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_TRANSFORMED
Definition: type_set.h:47
@ SYM_CONSOPTYPE_CARD_TUPLE
Definition: type_symmetry.h:87
@ SYM_CONSOPTYPE_SUM
Definition: type_symmetry.h:83
@ SYM_SYMTYPE_PERM
Definition: type_symmetry.h:61
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97