SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
cons_linking.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file cons_linking.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief constraint handler for linking constraints
28 * @author Stefan Heinz
29 * @author Jens Schulz
30 *
31 * The constraints handler stores linking constraints between a linking variable (integer or continuous) and an array of binary variables. Such
32 * a linking constraint has the form:
33 *
34 * linkvar = sum_{i=1}^n {vals[i] * binvars[i]}
35 *
36 * with the additional side condition that exactly one binary variable has to be one (set partitioning condition).
37 *
38 * This constraint can be created only with the linking variable if it is an integer variable. In this case the binary variables are only created on
39 * demand. That is, whenever someone asks for the binary variables. Therefore, such constraints can be used to get a
40 * "binary representation" of the domain of the linking variable which will be dynamically created.
41 *
42 *
43 * @todo add pairwise comparison of constraints in presolving (fast hash table version and complete pairwise comparison)
44 * @todo in case the integer variable is set to lower or upper bound it follows that only the corresponding binary
45 * variable has a positive value which is one, this can be used to fasten the checking routine
46 */
47
48/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
49
51#include "scip/cons_linear.h"
52#include "scip/cons_linking.h"
53#include "scip/cons_setppc.h"
54#include "scip/pub_cons.h"
55#include "scip/pub_event.h"
56#include "scip/pub_lp.h"
57#include "scip/pub_message.h"
58#include "scip/pub_misc.h"
59#include "scip/pub_misc_sort.h"
60#include "scip/pub_var.h"
61#include "scip/scip_conflict.h"
62#include "scip/scip_cons.h"
63#include "scip/scip_copy.h"
64#include "scip/scip_cut.h"
65#include "scip/scip_event.h"
66#include "scip/scip_general.h"
67#include "scip/scip_lp.h"
68#include "scip/scip_mem.h"
69#include "scip/scip_message.h"
70#include "scip/scip_nlp.h"
71#include "scip/scip_numerics.h"
72#include "scip/scip_param.h"
73#include "scip/scip_prob.h"
74#include "scip/scip_probing.h"
75#include "scip/scip_sol.h"
76#include "scip/scip_tree.h"
77#include "scip/scip_var.h"
78
79
80/* constraint handler properties */
81#define CONSHDLR_NAME "linking"
82#define CONSHDLR_DESC "linking constraint x = sum_{i=1}^{n} c_i*y_i, y1+...+yn = 1, x real, y's binary"
83
84#define EVENTHDLR_NAME "linking"
85#define EVENTHDLR_DESC "event handler for linking constraints"
86
87#define CONSHDLR_SEPAPRIORITY 750000 /**< priority of the constraint handler for separation */
88#define CONSHDLR_ENFOPRIORITY -2050000 /**< priority of the constraint handler for constraint enforcing */
89#define CONSHDLR_CHECKPRIORITY -750000 /**< priority of the constraint handler for checking feasibility */
90#define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
91#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
92#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only */
93#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
94#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
95#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
96#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
97
98#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
99#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
100
101
102#define HASHSIZE_BINVARSCONS 500 /**< minimal size of hash table in linking constraint handler */
103#define DEFAULT_LINEARIZE FALSE /**< should the linking constraint be linearize after the binary variable are created */
104
105/*
106 * Data structures
107 */
108
109/** constraint data for linking constraints */
110struct SCIP_ConsData
111{
112 SCIP_VAR* linkvar; /**< continuous variable which is linked */
113 SCIP_VAR** binvars; /**< binary variables */
114 SCIP_Real* vals; /**< coefficients */
115 SCIP_ROW* row1; /**< LP row for the linking itself */
116 SCIP_ROW* row2; /**< LP row ensuring the set partitioning condition of the binary variables */
117 SCIP_NLROW* nlrow1; /**< NLP row for the linking itself */
118 SCIP_NLROW* nlrow2; /**< NLP row ensuring the set partitioning condition of the binary variables */
119 int nbinvars; /**< number of binary variables */
120 int sizebinvars; /**< size of the binary variable array */
121 int nfixedzeros; /**< current number of variables fixed to zero in the constraint */
122 int nfixedones; /**< current number of variables fixed to one in the constraint */
123 int firstnonfixed; /**< index of first locally non-fixed binary variable in binvars array */
124 int lastnonfixed; /**< index of last locally non-fixed binary variable in binvars array */
125 unsigned int cliqueadded:1; /**< was the set partitioning condition already added as clique? */
126 unsigned int sorted:1; /**< are the coefficients of the binary variables are sorted in non-decreasing order */
127};
128
129/** constraint handler data */
130struct SCIP_ConshdlrData
131{
132 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events on binary variables */
133 SCIP_HASHMAP* varmap; /**< hash map mapping a linking variable to its linking constraint */
134 SCIP_Bool linearize; /**< should the linking constraint be linearize after the binary variable are created */
135};
136
137/*
138 * Local methods
139 */
140
141/** returns for a given linking variable the corresponding hash map key */
142static
144 SCIP_VAR* var /**< variable to get the hash map key for */
145 )
146{
147 /* return the unique variable index + 1 */
148 return (void*)(size_t)(SCIPvarGetIndex(var) + 1); /*lint !e571 !e776*/
149}
150
151/* sort binary variable in non-decreasing order w.r.t. coefficients */
152static
154 SCIP_CONSDATA* consdata /**< linking constraint data */
155 )
156{
157 if( consdata->sorted )
158 return;
159
160 /* sort binary variable in non-decreasing order w.r.t. coefficients */
161 SCIPsortRealPtr(consdata->vals, (void**)consdata->binvars, consdata->nbinvars);
162
163 consdata->sorted = TRUE;
164}
165
166
167/** installs rounding locks for the binary variables in the given linking constraint */
168static
170 SCIP* scip, /**< SCIP data structure */
171 SCIP_CONS* cons, /**< linking constraint */
172 SCIP_VAR** binvars, /**< binary variables */
173 int nbinvars /**< number of binary variables */
174 )
175{
176 int b;
177
178 for( b = 0; b < nbinvars; ++b )
179 {
180 SCIP_CALL( SCIPlockVarCons(scip, binvars[b], cons, TRUE, TRUE) );
181 }
182
183 return SCIP_OKAY;
184}
185
186/** creates constraint handler data for the linking constraint handler */
187static
189 SCIP* scip, /**< SCIP data structure */
190 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
191 SCIP_EVENTHDLR* eventhdlr /**< event handler */
192 )
193{
194 assert(scip != NULL);
195 assert(conshdlrdata != NULL);
196 assert(eventhdlr != NULL);
197
198 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
199
200 /* create hash map */
201 (*conshdlrdata)->varmap = NULL;
202
203 /* set event handler for bound change events on binary variables */
204 (*conshdlrdata)->eventhdlr = eventhdlr;
205
206 return SCIP_OKAY;
207}
208
209/** frees constraint handler data for linking constraint handler */
210static
212 SCIP* scip, /**< SCIP data structure */
213 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
214 )
215{
216 assert(conshdlrdata != NULL);
217 assert(*conshdlrdata != NULL);
218
219 /* free hash map */
220 if( (*conshdlrdata)->varmap != NULL )
221 SCIPhashmapFree(&(*conshdlrdata)->varmap);
222
223 /* free memory of constraint handler data */
224 SCIPfreeBlockMemory(scip, conshdlrdata);
225}
226
227/** prints linking constraint to file stream */
228static
230 SCIP* scip, /**< SCIP data structure */
231 SCIP_CONSDATA* consdata, /**< linking constraint data */
232 FILE* file /**< output file (or NULL for standard output) */
233 )
234{
235 SCIP_VAR** binvars;
236 SCIP_VAR* linkvar;
237 int nbinvars;
238
239 assert(scip != NULL);
240 assert(consdata != NULL);
241
242 linkvar = consdata->linkvar;
243 binvars = consdata->binvars;
244 nbinvars = consdata->nbinvars;
245
246 assert(linkvar != NULL);
247 assert(binvars != NULL || nbinvars == 0);
248
249 /* print linking variable */
250 SCIP_CALL( SCIPwriteVarName(scip, file, linkvar, FALSE) );
251
252 SCIPinfoMessage(scip, file, " = ");
253
254 if( nbinvars == 0 )
255 {
256 SCIPinfoMessage(scip, file, " no binary variables yet");
257 }
258 else
259 {
260 assert(binvars != NULL);
261
262 SCIP_CALL( SCIPwriteVarsLinearsum(scip, file, binvars, consdata->vals, nbinvars, FALSE) );
263 }
264
265 return SCIP_OKAY;
266}
267
268/** catches events for variable at given position */
269static
271 SCIP* scip, /**< SCIP data structure */
272 SCIP_CONSDATA* consdata, /**< linking constraint data */
273 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
274 int pos /**< array position of variable to catch bound change events for */
275 )
276{
277 SCIP_VAR* var;
278
279 assert(consdata != NULL);
280 assert(eventhdlr != NULL);
281 assert(0 <= pos && pos < consdata->nbinvars);
282 assert(consdata->binvars != NULL);
283
284 var = consdata->binvars[pos];
285 assert(var != NULL);
286
287 /* catch bound change events on variable */
288 /**@todo do we have to add the event SCIP_EVENTTYPE_VARFIXED? */
290
291 /* update the fixed variables counters for this variable */
292 if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
293 consdata->nfixedzeros++;
294 else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
295 consdata->nfixedones++;
296
297 return SCIP_OKAY;
298}
299
300/** drops events for variable at given position */
301static
303 SCIP* scip, /**< SCIP data structure */
304 SCIP_CONSDATA* consdata, /**< linking constraint data */
305 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
306 int pos /**< array position of variable to catch bound change events for */
307 )
308{
309 SCIP_VAR* var;
310
311 assert(consdata != NULL);
312 assert(eventhdlr != NULL);
313 assert(0 <= pos && pos < consdata->nbinvars);
314 assert(consdata->binvars != NULL);
315
316 var = consdata->binvars[pos];
317 assert(var != NULL);
318
319 /* drop events on variable */
321
322 /* update the fixed variables counters for this variable */
323 if( SCIPisEQ(scip, SCIPvarGetUbLocal(var), 0.0) )
324 consdata->nfixedzeros--;
325 else if( SCIPisEQ(scip, SCIPvarGetLbLocal(var), 1.0) )
326 consdata->nfixedones--;
327
328 return SCIP_OKAY;
329}
330
331/** catches bound change events for all variables in transformed linking constraint */
332static
334 SCIP* scip, /**< SCIP data structure */
335 SCIP_CONSDATA* consdata, /**< linking constraint data */
336 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
337 )
338{
339 int i;
340
341 assert(consdata != NULL);
342
343 /* author bzfhende
344 *
345 * TODO should we catch events even in the trivial case of only 1 binary variable
346 */
347
348 /* catch event for every single variable */
349 for( i = 0; i < consdata->nbinvars; ++i )
350 {
351 SCIP_CALL( catchEvent(scip, consdata, eventhdlr, i) );
352 }
353
354 return SCIP_OKAY;
355}
356
357/** drops bound change events for all variables in transformed linking constraint */
358static
360 SCIP* scip, /**< SCIP data structure */
361 SCIP_CONSDATA* consdata, /**< linking constraint data */
362 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
363 )
364{
365 int i;
366
367 assert(consdata != NULL);
368
369 /* author bzfhende
370 *
371 * TODO drop the events even in the trivial case nbinvars == 1?
372 */
373
374 /* drop event of every single variable */
375 for( i = 0; i < consdata->nbinvars; ++i )
376 {
377 SCIP_CALL( dropEvent(scip, consdata, eventhdlr, i) );
378 }
379
380 return SCIP_OKAY;
381}
382
383/** linearize the given linking constraint into a set partitioning constraint for the binary variables and a linear
384 * constraint for the linking between the linking variable and the binary variables */
385static
387 SCIP* scip, /**< SCIP data structure */
388 SCIP_CONS* cons, /**< linking constraint */
389 SCIP_CONSDATA* consdata /**< linking constraint data */
390 )
391{
392 SCIP_CONS* lincons;
393 int b;
394
395 SCIPdebugMsg(scip, "linearized linking constraint <%s>\n", SCIPconsGetName(cons));
396
397 /* create set partitioning constraint for the binary variables */
398 SCIP_CALL( SCIPcreateConsSetpart(scip, &lincons, SCIPconsGetName(cons), consdata->nbinvars, consdata->binvars,
402 SCIP_CALL( SCIPaddCons(scip, lincons) );
403 SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
404
405 /* create linear constraint for the linking between the binary variables and the linking variable */
406 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons), 0, NULL, NULL, 0.0, 0.0,
410
411 for( b = 0; b < consdata->nbinvars; ++b )
412 {
413 SCIP_CALL( SCIPaddCoefLinear(scip, lincons, consdata->binvars[b], consdata->vals[b]) );
414 }
415 SCIP_CALL( SCIPaddCoefLinear(scip, lincons, consdata->linkvar, -1.0) );
416
417 SCIP_CALL( SCIPaddCons(scip, lincons) );
418 SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
419
420 return SCIP_OKAY;
421}
422
423/** creates the binary variables */
424static
426 SCIP* scip, /**< SCIP data structure */
427 SCIP_CONS* cons, /**< linking constraint */
428 SCIP_CONSDATA* consdata, /**< linking constraint data */
429 SCIP_EVENTHDLR* eventhdlr, /**< event handler for bound change events on binary variables */
430 SCIP_Bool linearize /**< should the linking constraint be linearized */
431 )
432{
433 SCIP_VAR* linkvar;
434 SCIP_VAR* binvar;
435 int lb;
436 int ub;
437 char name[SCIP_MAXSTRLEN];
438 int nbinvars;
439 int b;
440
441 assert(scip != NULL);
442 assert(consdata != NULL);
443 assert(consdata->nbinvars == 0);
444 assert(consdata->binvars == NULL);
445
446 SCIPdebugMsg(scip, "create binary variables for linking variable <%s>\n", SCIPvarGetName(consdata->linkvar));
447
448 /* author bzfhende
449 *
450 * TODO ensure that this method is only called for integer linking variables, because it does not make sense for continuous linking variables.
451 */
452
453 linkvar = consdata->linkvar;
456
457 nbinvars = ub - lb + 1;
458 assert(nbinvars > 0);
459
460 /* allocate block memory for the binary variables */
461 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->binvars, nbinvars) );
462 /* allocate block memory for the binary variables */
463 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vals, nbinvars) );
464 consdata->sizebinvars = nbinvars;
465
466 /* check if the linking variable is fixed */
467 if( nbinvars == 1 )
468 {
469 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d]", SCIPvarGetName(linkvar), lb);
470
471 /* creates and captures a fixed binary variables */
472 SCIP_CALL( SCIPcreateVar(scip, &binvar, name, 1.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
473 FALSE, TRUE, NULL, NULL, NULL, NULL, NULL) );
474 SCIP_CALL( SCIPaddVar(scip, binvar) );
475
476 consdata->binvars[0] = binvar;
477 consdata->vals[0] = lb;
478 }
479 else
480 {
481 for( b = 0; b < nbinvars; ++b)
482 {
483 (void)SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s[%d]", SCIPvarGetName(linkvar), lb + b);
484
485 /* creates and captures variables */
486 SCIP_CALL( SCIPcreateVar(scip, &binvar, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_BINARY,
487 TRUE, TRUE, NULL, NULL, NULL, NULL, NULL) );
488
489 /* add variable to the problem */
490 SCIP_CALL( SCIPaddVar(scip, binvar) );
491 consdata->binvars[b] = binvar;
492 consdata->vals[b] = lb + b;
493 }
494 }
495
496 consdata->nbinvars = nbinvars;
497
498 assert(consdata->nfixedzeros == 0);
499 assert(consdata->nfixedones == 0);
500
502 {
503 /* (rounding) lock binary variable */
504 SCIP_CALL( lockRounding(scip, cons, consdata->binvars, consdata->nbinvars) );
505
506 /* catch bound change events of variables */
507 SCIP_CALL( catchAllEvents(scip, consdata, eventhdlr) );
508
509 if( nbinvars > 1 )
510 {
511 if( linearize )
512 {
513 SCIP_CALL( consdataLinearize(scip, cons, consdata) );
514 }
515 else
516 {
517 /* enable constraint */
518 SCIP_CALL( SCIPenableCons(scip, cons) );
519 }
520 }
521 }
522
523 return SCIP_OKAY;
524}
525
526/** creates consdata */
527static
529 SCIP* scip, /**< SCIP data structure */
530 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
531 SCIP_CONSDATA** consdata, /**< pointer to constraint data */
532 SCIP_VAR* linkvar, /**< linking variable which is linked */
533 SCIP_VAR** binvars, /**< binary variables */
534 SCIP_Real* vals, /**< coefficients of the binary variables */
535 int nbinvars /**< number of binary starting variables */
536 )
537{
538 int v;
539
540 assert(scip!= NULL);
541 assert(consdata != NULL);
542 assert(linkvar != NULL);
543 assert(binvars != NULL || nbinvars == 0);
545
546 /* allocate memory for consdata */
547 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
548
549 (*consdata)->linkvar = linkvar;
550 (*consdata)->nbinvars = nbinvars;
551 (*consdata)->sizebinvars = nbinvars;
552 (*consdata)->row1 = NULL;
553 (*consdata)->row2 = NULL;
554 (*consdata)->nlrow1 = NULL;
555 (*consdata)->nlrow2 = NULL;
556 (*consdata)->cliqueadded = FALSE;
557
558 /* initialize constraint state */
559 (*consdata)->sorted = FALSE;
560 (*consdata)->firstnonfixed = 0;
561 (*consdata)->lastnonfixed = nbinvars - 1;
562 (*consdata)->nfixedzeros = 0;
563 (*consdata)->nfixedones = 0;
564
565 if( nbinvars == 0 )
566 {
567 (*consdata)->binvars = NULL;
568 (*consdata)->vals = NULL;
569 }
570 else
571 {
572 /* copy binary variable array */
573 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->binvars, binvars, nbinvars) );
574
575 /* copy coefficients */
576 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vals, vals, nbinvars) );
577 }
578
579 /* get transformed variable, if we are in the transformed problem */
581 {
582 if( nbinvars > 0 )
583 {
584 SCIP_CALL( SCIPgetTransformedVars(scip, nbinvars, (*consdata)->binvars, (*consdata)->binvars) );
585
586 /* catch bound change events of variables */
587 SCIP_CALL( catchAllEvents(scip, *consdata, eventhdlr) );
588 }
589
590 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->linkvar, &(*consdata)->linkvar) );
591 }
592
593 /* author bzfhende
594 *
595 * TODO do we need to forbid multi-aggregations? This was only needed if we substitute and resubstitute linking
596 * variables into linear constraints.
597 */
598
599 /* capture variables */
600 for( v = 0; v < nbinvars; ++v )
601 {
602 assert((*consdata)->binvars[v] != NULL);
603 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->binvars[v]) );
604 }
605 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->linkvar) );
606
607 return SCIP_OKAY;
608}
609
610
611/** free consdata */
612static
614 SCIP* scip, /**< SCIP data structure */
615 SCIP_CONSDATA** consdata /**< pointer to consdata */
616 )
617{
618 int v;
619
620 assert(consdata != NULL);
621 assert(*consdata != NULL);
622 assert((*consdata)->nbinvars == 0 || (*consdata)->binvars != NULL);
623
624 /* release the rows */
625 if( (*consdata)->row1 != NULL )
626 {
627 assert((*consdata)->row2 != NULL);
628
629 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row1) );
630 SCIP_CALL( SCIPreleaseRow(scip, &(*consdata)->row2) );
631 }
632
633 /* release the nlrows */
634 if( (*consdata)->nlrow1 != NULL )
635 {
636 assert((*consdata)->nlrow2 != NULL);
637
638 SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow1) );
639 SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow2) );
640 }
641
642 /* capture variables */
643 for( v = 0; v < (*consdata)->nbinvars; ++v )
644 {
645 assert((*consdata)->binvars[v] != NULL);
646 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->binvars[v]) );
647 }
648 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->linkvar) );
649
650 /* free binary variable array */
651 if( (*consdata)->sizebinvars > 0 )
652 {
653 /* if constraint belongs to transformed problem space, drop bound change events on variables */
654 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vals, (*consdata)->sizebinvars);
655 SCIPfreeBlockMemoryArray(scip, &(*consdata)->binvars, (*consdata)->sizebinvars);
656 }
657
658 /* check if the fixed counters are reset */
659 assert((*consdata)->nfixedzeros == 0);
660 assert((*consdata)->nfixedones == 0);
661
662 /* free constraint data */
663 SCIPfreeBlockMemory(scip, consdata);
664
665 return SCIP_OKAY;
666}
667
668
669/** analyzes conflicting assignment on given constraint where reason comes from the linking variable lower or upper
670 * bound
671 */
672static
674 SCIP* scip, /**< SCIP data structure */
675 SCIP_CONS* cons, /**< linking constraint to be processed */
676 SCIP_VAR* linkvar, /**< linking variable */
677 SCIP_VAR* binvar, /**< binary variable is the reason */
678 SCIP_Bool lblinkvar, /**< lower bound of linking variable is the reason */
679 SCIP_Bool ublinkvar /**< upper bound of linking variable is the reason */
680 )
681{
682 assert(scip != NULL);
683
684 /* conflict analysis can only be applied in solving stage and if it is turned on */
686 return SCIP_OKAY;
687
688 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
690
691 if( lblinkvar )
692 {
693 assert(linkvar != NULL);
694 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, NULL) );
695 }
696
697 if( ublinkvar )
698 {
699 assert(linkvar != NULL);
700 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, NULL) );
701 }
702
703 if( binvar != NULL )
704 {
706 }
707
708 /* analyze the conflict */
710
711 return SCIP_OKAY;
712}
713
714/* author bzfhende
715 *
716 * TODO check if the method below produces valid results even if the variable is continuous
717 */
718
719/** fix linking variable to the value of the binary variable at pos */
720static
722 SCIP* scip, /**< SCIP data structure */
723 SCIP_CONS* cons, /**< linking constraint to be processed */
724 int pos, /**< position of binary variable */
725 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
726 )
727{
728 SCIP_CONSDATA* consdata;
729 SCIP_VAR* linkvar;
730 SCIP_Bool infeasible;
731 SCIP_Bool tightened;
732 SCIP_Real coef;
733
734 consdata = SCIPconsGetData(cons);
735 assert(consdata != NULL);
736
737 linkvar = consdata->linkvar;
738 coef = consdata->vals[pos];
739
740 /* change lower bound of the linking variable */
741 SCIP_CALL( SCIPinferVarLbCons(scip, linkvar, coef, cons, pos, TRUE, &infeasible, &tightened) );
742
743 if( infeasible )
744 {
745 assert(coef > SCIPvarGetUbLocal(linkvar));
746 assert(coef >= SCIPvarGetLbLocal(linkvar));
747
748 SCIP_CALL( analyzeConflict(scip, cons, linkvar, consdata->binvars[pos], FALSE, TRUE) );
749
750 *cutoff = TRUE;
751 return SCIP_OKAY;
752 }
753 assert(SCIPisFeasLE(scip, coef, SCIPvarGetUbLocal(linkvar)));
754
755 /* change upper bound of the integer variable */
756 SCIP_CALL( SCIPinferVarUbCons(scip, linkvar, coef, cons, pos, TRUE, &infeasible, &tightened) );
757
758 if( infeasible )
759 {
760 assert(coef < SCIPvarGetLbLocal(linkvar));
761 assert(coef <= SCIPvarGetUbLocal(linkvar));
762
763 SCIP_CALL( analyzeConflict(scip, cons, linkvar, consdata->binvars[pos], TRUE, FALSE) );
764
765 *cutoff = TRUE;
766 return SCIP_OKAY;
767 }
768
770
771 return SCIP_OKAY;
772}
773
774/** checks constraint for violation from the local bound of the linking variable, applies fixings to the binary
775 * variables if possible
776 */
777static
779 SCIP* scip, /**< SCIP data structure */
780 SCIP_CONS* cons, /**< linking constraint to be processed */
781 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
782 int* nchgbds, /**< pointer to store the number of changes (foxed) variable bounds */
783 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
784 )
785{
786 SCIP_CONSDATA* consdata;
787 SCIP_VAR** binvars;
788 SCIP_VAR* linkvar;
789 SCIP_Real* vals;
790 SCIP_Real lb;
791 SCIP_Real ub;
792 int nbinvars;
793 int b;
794 SCIP_Bool infeasible;
795 SCIP_Bool tightened;
796
797 assert(cons != NULL);
798 assert(SCIPconsGetHdlr(cons) != NULL);
800 assert(cutoff != NULL);
801 assert(nchgbds != NULL);
803
804 consdata = SCIPconsGetData(cons);
805 assert(consdata != NULL);
806
807 /* ensure that the binary variables are sorted in non-decreasing order w.r.t. their coefficients */
808 consdataSort(consdata);
809
810 nbinvars = consdata->nbinvars;
811
812 /* in case there is only at most one binary variables, the constraints should already be disabled */
813 assert(nbinvars > 1);
814
815 /* if more than one binary variable is fixed to one or at least nbinvars minus one variable are fixed to zero */
816 if( consdata->nfixedones > 0 || consdata->nfixedzeros >= nbinvars-1 )
817 return SCIP_OKAY;
818
819 linkvar = consdata->linkvar;
820 assert(linkvar != NULL);
821
822 binvars = consdata->binvars;
823 vals = consdata->vals;
824
825 lb = SCIPvarGetLbLocal(linkvar);
826 ub = SCIPvarGetUbLocal(linkvar);
827
828 assert(lb <= ub);
829
830#ifndef NDEBUG
831 /* check that the first variable are locally fixed to zero */
832 for( b = 0; b < consdata->firstnonfixed; ++b )
833 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
834
835 /* check that the last variable are locally fixed to zero */
836 for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b )
837 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
838#endif
839
840 for( b = consdata->firstnonfixed; b < nbinvars; ++b )
841 {
842 if( SCIPisLT(scip, vals[b], lb) )
843 {
844 SCIP_VAR* var;
845
846 var = binvars[b];
847 assert(var != NULL);
848
849 SCIPdebugMsg(scip, "fix variable <%s> to zero due to the lower bound of the linking variable <%s> [%g,%g]\n",
850 SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub);
851
852 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -2, &infeasible, &tightened) );
853
854 if( infeasible )
855 {
856 SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, TRUE, FALSE) );
857 *cutoff = TRUE;
858 return SCIP_OKAY;
859 }
860
861 if( tightened )
862 (*nchgbds)++;
863
864 /* adjust constraint state */
865 consdata->firstnonfixed++;
866 }
867 else
868 break;
869 }
870
871 /* fix binary variables to zero if not yet fixed, from local upper bound + 1*/
872 for( b = consdata->lastnonfixed; b >= 0; --b )
873 {
874 if( SCIPisGT(scip, vals[b], ub) )
875 {
876 SCIP_VAR* var;
877
878 var = binvars[b];
879 assert(var != NULL);
880
881 SCIPdebugMsg(scip, "fix variable <%s> to zero due to the upper bound of the linking variable <%s> [%g,%g]\n",
882 SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub);
883
884 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -3, &infeasible, &tightened) );
885
886 if( infeasible )
887 {
888 SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, FALSE, TRUE) );
889 *cutoff = TRUE;
890 return SCIP_OKAY;
891 }
892
893 if( tightened )
894 (*nchgbds)++;
895
896 /* adjust constraint state */
897 consdata->lastnonfixed--;
898 }
899 else
900 break;
901 }
902
903 if( consdata->firstnonfixed > consdata->lastnonfixed )
904 {
905 *cutoff = TRUE;
906 return SCIP_OKAY;
907 }
908
909 *mustcheck = (*nchgbds) == 0;
910
911 /* if linking variable is fixed, create for the binary variables which have a coefficient equal to the fixed value a
912 * set partitioning constraint
913 */
914 if( SCIPisEQ(scip, lb, ub) )
915 {
916 if( consdata->firstnonfixed == consdata->lastnonfixed )
917 {
918 SCIP_VAR* var;
919
920 var = binvars[consdata->firstnonfixed];
921
922 SCIPdebugMsg(scip, "fix variable <%s> to one due to the fixed linking variable <%s> [%g,%g]\n",
923 SCIPvarGetName(var), SCIPvarGetName(linkvar), lb, ub);
924
925 /* TODO can the forbidden cases be covered more elegantly? */
927 return SCIP_OKAY;
928
932 return SCIP_OKAY;
933
934 SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, -6, &infeasible, &tightened) );
935
936 if( infeasible )
937 {
938 SCIP_CALL( analyzeConflict(scip, cons, linkvar, var, TRUE, TRUE) );
939 *cutoff = TRUE;
940 return SCIP_OKAY;
941 }
942
943 if( tightened )
944 (*nchgbds)++;
945
946 SCIPdebugMsg(scip, " -> disabling linking constraint <%s>\n", SCIPconsGetName(cons));
948
949 *mustcheck = FALSE;
950 }
951 else if( SCIPgetDepth(scip) <= 0 )
952 {
954 SCIP_VAR** vars;
955 int nvars;
956
957 /* get sub array of variables which have the same coefficient */
958 vars = &consdata->binvars[consdata->firstnonfixed];
959 nvars = consdata->lastnonfixed - consdata->firstnonfixed + 1;
960
965
968
970 }
971 }
972
973 return SCIP_OKAY;
974}
975
976/** deletes coefficient at given position from the binary variable array */
977static
979 SCIP* scip, /**< SCIP data structure */
980 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
981 SCIP_CONS* cons, /**< linking constraint */
982 int pos /**< position of coefficient to delete */
983 )
984{
985 SCIP_CONSDATA* consdata;
986 SCIP_VAR* var;
987
988 assert(scip != NULL);
989 assert(eventhdlr != NULL);
990
991 consdata = SCIPconsGetData(cons);
992 assert(consdata != NULL);
993 assert(0 <= pos && pos < consdata->nbinvars);
994
995 var = consdata->binvars[pos];
996 assert(var != NULL);
998
999 /* remove the rounding locks for the deleted variable */
1001
1002 /* if we are in transformed problem, delete the event data of the variable */
1003 if( SCIPconsIsTransformed(cons) )
1004 {
1005 SCIP_CONSHDLR* conshdlr;
1006 SCIP_CONSHDLRDATA* conshdlrdata;
1007
1008 /* get event handler */
1009 conshdlr = SCIPconsGetHdlr(cons);
1010 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1011 assert(conshdlrdata != NULL);
1012 assert(conshdlrdata->eventhdlr != NULL);
1013
1014 /* drop bound change events of variable */
1015 SCIP_CALL( dropEvent(scip, consdata, conshdlrdata->eventhdlr, pos) );
1016 }
1017
1018 /* move the last variable to the free slot */
1019 if( pos != consdata->nbinvars - 1 )
1020 {
1021 consdata->binvars[pos] = consdata->binvars[consdata->nbinvars-1];
1022 consdata->vals[pos] = consdata->vals[consdata->nbinvars-1];
1023 consdata->sorted = FALSE;
1024 }
1025
1026 consdata->nbinvars--;
1027
1028 /* release variable */
1030
1031 return SCIP_OKAY;
1032}
1033
1034/** remove the trailing and leading binary variables that are fixed to zero */
1035static
1037 SCIP* scip, /**< SCIP data structure */
1038 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1039 SCIP_CONS* cons /**< linking constraint */
1040 )
1041{
1042 SCIP_CONSDATA* consdata;
1043 int nbinvars;
1044 int b;
1045
1046 consdata = SCIPconsGetData(cons);
1047 assert(consdata != NULL);
1048 assert(consdata->sorted);
1049
1053
1054 nbinvars = consdata->nbinvars;
1055
1056 for( b = nbinvars - 1; b > consdata->lastnonfixed; --b )
1057 {
1058 SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) );
1059 }
1060
1061 for( b = consdata->firstnonfixed - 1; b >= 0; --b )
1062 {
1063 SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) );
1064 }
1065
1066 for( b = consdata->nbinvars - 1; b >= 0; --b )
1067 {
1068 if( SCIPvarGetUbLocal(consdata->binvars[b]) < 0.5 )
1069 {
1070 SCIP_CALL( delCoefPos(scip, eventhdlr, cons, b) );
1071 }
1072 }
1073
1074 /* set the constraint state */
1075 consdata->firstnonfixed = 0;
1076 consdata->lastnonfixed = consdata->nbinvars - 1;
1077
1078 return SCIP_OKAY;
1079}
1080
1081/** tightened the linking variable due to binary variables which are fixed to zero */
1082static
1084 SCIP* scip, /**< SCIP data structure */
1085 SCIP_CONS* cons, /**< linking constraint to be processed */
1086 SCIP_CONSDATA* consdata, /**< linking constraint to be processed */
1087 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1088 int* nchgbds /**< pointer to store the number of changed variable bounds */
1089 )
1090{
1091 SCIP_VAR** binvars;
1092 SCIP_VAR* linkvar;
1093 SCIP_Real* vals;
1094
1095 SCIP_Bool infeasible;
1096 SCIP_Bool tightened;
1097 int nbinvars;
1098 int b;
1099
1100 /* if more than one binary variable is fixed to one or at least nbinvars minus one variable are fixed to zero return */
1101 if( consdata->nfixedones > 1 || consdata->nfixedzeros >= consdata->nbinvars-1 )
1102 return SCIP_OKAY;
1103
1104 if( *cutoff )
1105 return SCIP_OKAY;
1106
1107 assert(consdata->sorted);
1108
1109 linkvar = consdata->linkvar;
1110 binvars = consdata->binvars;
1111 vals = consdata->vals;
1112 nbinvars = consdata->nbinvars;
1113
1114#ifndef NDEBUG
1115 /* check that the first variable are locally fixed to zero */
1116 for( b = 0; b < consdata->firstnonfixed; ++b )
1117 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
1118#endif
1119
1120 assert(consdata->firstnonfixed < nbinvars);
1121 assert(consdata->lastnonfixed < nbinvars);
1122
1123 /* find first non fixed binary variable */
1124 for( b = consdata->firstnonfixed; b < nbinvars; ++b )
1125 {
1126 if( SCIPvarGetUbLocal(binvars[b]) > 0.5 )
1127 break;
1128
1129 consdata->firstnonfixed++;
1130 }
1131
1132 SCIP_CALL( SCIPinferVarLbCons(scip, linkvar, vals[b], cons, -4, TRUE, &infeasible, &tightened) );
1133
1134 /* start conflict analysis if infeasible */
1135 if( infeasible )
1136 {
1137 /* analyze the cutoff if if SOLVING stage and conflict analysis is turned on */
1139 {
1140 SCIPdebugMsg(scip, "conflict at <%s> due to bounds and fixed binvars: [lb,ub] = [%g,%g]; b= %d; coef = %g \n",
1141 SCIPvarGetName(linkvar), SCIPvarGetLbLocal(linkvar), SCIPvarGetUbLocal(linkvar), b, vals[b]);
1142
1144
1145 /* ??????????? use resolve method and only add binvars which are needed to exceed the upper bound */
1146
1147 /* add conflicting variables */
1148 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, NULL) );
1149
1150 for( b = 0; b < consdata->firstnonfixed; ++b )
1151 {
1152 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
1153 }
1154
1155 /* analyze the conflict */
1157 }
1158
1159 *cutoff = TRUE;
1160 return SCIP_OKAY;
1161 }
1162
1163 if( tightened )
1164 (*nchgbds)++;
1165
1166#ifndef NDEBUG
1167 /* check that the last variable are locally fixed to zero */
1168 for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b )
1169 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
1170#endif
1171
1172 /* find last non fixed variable */
1173 for( b = consdata->lastnonfixed; b >= 0; --b )
1174 {
1175 if( SCIPvarGetUbLocal(binvars[b]) > 0.5 )
1176 break;
1177
1178 consdata->lastnonfixed--;
1179 }
1180
1182 SCIP_CALL( SCIPinferVarUbCons(scip, linkvar, (SCIP_Real)vals[b], cons, -5, TRUE, &infeasible, &tightened) );
1183
1184 if( infeasible )
1185 {
1186 /* conflict analysis can only be applied in solving stage and if conflict analysis is turned on */
1188 {
1189 SCIPdebugMsg(scip, "conflict at <%s> due to bounds and fixed binvars: [lb,ub] = [%g,%g]; b = %d; coef = %g,\n",
1190 SCIPvarGetName(linkvar), SCIPvarGetLbLocal(linkvar), SCIPvarGetUbLocal(linkvar), b, vals[b]);
1191
1193
1194 /* ??????????? use resolve method and only add binvars which are needed to fall below the lower bound */
1195
1196 /* add conflicting variables */
1197 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, NULL) );
1198
1199 for( b = consdata->lastnonfixed + 1; b < nbinvars; ++b )
1200 {
1201 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
1202 }
1203
1204 /* analyze the conflict */
1206 }
1207
1208 *cutoff = TRUE;
1209 return SCIP_OKAY;
1210 }
1211
1212 if( tightened )
1213 (*nchgbds)++;
1214
1215 return SCIP_OKAY;
1216}
1217
1218/** checks constraint for violation only looking at the fixed binary variables, applies further fixings if possible */
1219static
1221 SCIP* scip, /**< SCIP data structure */
1222 SCIP_CONS* cons, /**< linking constraint to be processed */
1223 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1224 int* nchgbds, /**< pointer to store the number of changed variable bounds */
1225 SCIP_Bool* addcut, /**< pointer to store whether this constraint must be added as a cut */
1226 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
1227 )
1228{
1229 SCIP_CONSDATA* consdata;
1230 SCIP_Bool infeasible;
1231 SCIP_Bool tightened;
1232
1233 assert(cons != NULL);
1234 assert(SCIPconsGetHdlr(cons) != NULL);
1236 assert(cutoff != NULL);
1237 assert(nchgbds != NULL);
1238 assert(addcut != NULL);
1239 assert(mustcheck != NULL);
1240
1241 consdata = SCIPconsGetData(cons);
1242 assert(consdata != NULL);
1243 assert(consdata->nbinvars == 0 || consdata->binvars != NULL);
1244 assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nbinvars);
1245 assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nbinvars);
1246
1247 /* ensure that the binary variables are sorted in non-decreasing order w.r.t. their coefficients */
1248 consdataSort(consdata);
1249
1250 /* in case there is only at most one binary variables, the constraints should already be disabled */
1251 assert(consdata->nbinvars > 1);
1252
1253 if( *cutoff )
1254 return SCIP_OKAY;
1255
1256 if( consdata->nfixedones == 1 )
1257 {
1258 /* exactly one variable is fixed to 1:
1259 * - all other binary variables in a set partitioning must be zero
1260 * - linking variable is fixed to that binary variable
1261 */
1262 if( consdata->nfixedzeros < consdata->nbinvars - 1 ||
1263 SCIPisLT(scip, SCIPvarGetLbLocal(consdata->linkvar), SCIPvarGetUbLocal(consdata->linkvar)) )
1264 {
1265 SCIP_VAR** vars;
1266 SCIP_VAR* var;
1267#ifndef NDEBUG
1268 SCIP_Bool fixedonefound;
1269#endif
1270 int nvars;
1271 int v;
1272
1273 SCIPdebugMsg(scip, " -> fixing all other variables to zero due to the set partitioning condition <%s>\n",
1274 SCIPconsGetName(cons));
1275
1276 /* unfixed variables exist: fix them to zero;
1277 * this could result in additional variables fixed to one due to aggregations; in this case, the
1278 * constraint is infeasible in local bounds
1279 */
1280 vars = consdata->binvars;
1281 nvars = consdata->nbinvars;
1282#ifndef NDEBUG
1284#endif
1285
1286 for( v = 0; v < nvars && consdata->nfixedones == 1 && !(*cutoff); ++v )
1287 {
1288 var = vars[v];
1290 /* TODO can this be handled more elegantly? */
1292 continue;
1293
1297 continue;
1298
1299 if( SCIPvarGetLbLocal(var) < 0.5 )
1300 {
1301 SCIP_CALL( SCIPinferBinvarCons(scip, var, FALSE, cons, -1, &infeasible, &tightened) );
1302 assert(!infeasible);
1303 SCIPdebugMsg(scip, " -> fixed <%s> to zero (tightened=%u)\n", SCIPvarGetName(var), tightened);
1304 }
1305 else
1306 {
1307#ifndef NDEBUG
1309#endif
1310 /* fix linking variable */
1311 /* TODO check if variable status allows fixing (probably in consFixLinkvar) */
1312 SCIP_CALL( consFixLinkvar(scip, cons, v, cutoff) );
1313 }
1314 }
1315 if( !(*cutoff) )
1316 {
1317 /* the fixed to one variable must have been found, and at least one variable must have been fixed */
1318 assert(consdata->nfixedones >= 1 || fixedonefound);
1319
1321 (*nchgbds)++;
1322 }
1323 }
1324
1325 /* now all other variables are fixed to zero:
1326 * the constraint is feasible, and if it's not modifiable, it is redundant
1327 */
1328 if( !SCIPconsIsModifiable(cons) && consdata->nfixedones == 1 )
1329 {
1330 SCIPdebugMsg(scip, " -> disabling set linking constraint <%s>\n", SCIPconsGetName(cons));
1332 }
1333 }
1334 else if( consdata->nfixedones >= 2 )
1335 {
1336 /* at least two variables are fixed to 1:
1337 * - the set partitioning condition is violated
1338 */
1339 SCIPdebugMsg(scip, " -> conflict on " CONSHDLR_NAME " constraint <%s> due to the set partitioning condition\n", SCIPconsGetName(cons));
1340
1342
1343 /* conflict analysis can only be applied in solving stage and if it is applicable */
1345 {
1346 SCIP_VAR** vars;
1347 int nvars;
1348 int n;
1349 int v;
1350
1351 vars = consdata->binvars;
1352 nvars = consdata->nbinvars;
1353
1354 /* initialize conflict analysis, and add the two variables assigned to one to conflict candidate queue */
1356
1357 n = 0;
1358
1359 for( v = 0; v < nvars && n < 2; ++v )
1360 {
1361 if( SCIPvarGetLbLocal(vars[v]) > 0.5 )
1362 {
1364 n++;
1365 }
1366 }
1367 assert(n == 2);
1368
1369 /* analyze the conflict */
1371 }
1372
1373 *cutoff = TRUE;
1374 }
1375 else if( consdata->nfixedzeros == consdata->nbinvars )
1376 {
1377 /* all variables are fixed to zero:
1378 * - the set partitioning condition is violated, and if it's unmodifiable, the node
1379 * can be cut off -- otherwise, the constraint must be added as a cut and further pricing must
1380 * be performed
1381 */
1382 assert(consdata->nfixedones == 0);
1383
1384 SCIPdebugMsg(scip, " -> " CONSHDLR_NAME " constraint <%s> is infeasible due to the set partitioning condition\n",
1385 SCIPconsGetName(cons));
1386
1388 if( SCIPconsIsModifiable(cons) )
1389 *addcut = TRUE;
1390 else
1391 {
1392 /* conflict analysis can only be applied in solving stage and if it is applicable */
1394 {
1395 SCIP_VAR** vars;
1396 int nvars;
1397 int v;
1398
1399 vars = consdata->binvars;
1400 nvars = consdata->nbinvars;
1401
1402 /* initialize conflict analysis, add all variables of infeasible constraint to conflict candidate queue */
1404
1405 for( v = 0; v < nvars; ++v )
1406 {
1407 assert(SCIPvarGetUbLocal(vars[v]) < 0.5);
1409 }
1410
1411 /* analyze the conflict */
1413 }
1414 *cutoff = TRUE;
1415 }
1416 }
1417 else if( consdata->nfixedzeros == consdata->nbinvars - 1 )
1418 {
1419 /* all variables except one are fixed to zero:
1420 * - an unmodifiable set partitioning constraint is feasible and can be disabled after the
1421 * remaining variable is fixed to one
1422 * - a modifiable set partitioning constraint must be checked manually
1423 */
1424 assert(consdata->nfixedones == 0);
1425
1426 if( !SCIPconsIsModifiable(cons) )
1427 {
1428 SCIP_VAR** vars;
1429 SCIP_VAR* var;
1430 int nvars;
1431 int v;
1432
1433 /* search the single variable that can be fixed */
1434 vars = consdata->binvars;
1435 nvars = consdata->nbinvars;
1436 for( v = 0; v < nvars && !(*cutoff); ++v )
1437 {
1438 var = vars[v];
1441
1442 if( SCIPvarGetUbLocal(var) > 0.5 )
1443 {
1445 SCIPdebugMsg(scip, " -> fixing remaining binary variable <%s> to one in " CONSHDLR_NAME " constraint <%s>\n",
1447
1449 {
1450 SCIP_CALL( SCIPinferBinvarCons(scip, var, TRUE, cons, -1, &infeasible, &tightened) );
1451 assert(!infeasible);
1452 assert(tightened);
1453 }
1454
1455 /* fix linking variable */
1456 /* TODO check if variable status allows fixing (probably in consFixLinkvar)*/
1457 SCIP_CALL( consFixLinkvar(scip, cons, v, cutoff) );
1458 break;
1459 }
1460 }
1461 assert(v < nvars);
1462 assert(consdata->nfixedzeros == consdata->nbinvars - 1);
1463 assert(consdata->nfixedones == 1);
1464
1466 (*nchgbds)++;
1467 }
1468 }
1469 else
1470 {
1471 SCIP_CALL( tightenedLinkvar(scip, cons, consdata, cutoff, nchgbds) );
1472 }
1473
1474 *mustcheck = (*nchgbds) == 0;
1475
1476 assert(consdata->nfixedzeros + consdata->nfixedones <= consdata->nbinvars);
1477
1478 return SCIP_OKAY;
1479}
1480
1481/** returns whether the given solution is feasible for the given linking constraint */
1482static
1483SCIP_Bool checkCons(
1484 SCIP* scip, /**< SCIP data structure */
1485 SCIP_CONS* cons, /**< linking constraint to be checked */
1486 SCIP_SOL* sol /**< primal solution, or NULL for current LP/pseudo solution */
1487 )
1488{
1489 SCIP_CONSDATA* consdata;
1490 SCIP_VAR** binvars;
1491 SCIP_Real* vals;
1492 SCIP_Real solval;
1493 SCIP_Real linksum;
1494 SCIP_Real linkvarval;
1495 SCIP_Real setpartsum;
1496 SCIP_Real setpartsumbound;
1497 SCIP_Real absviol;
1498 SCIP_Real relviol;
1499 int nbinvars;
1500 int b;
1501
1502 assert(scip != NULL);
1503 assert(cons != NULL);
1504
1505 SCIPdebugMsg(scip, "checking linking constraint <%s> for feasibility of solution %p\n", SCIPconsGetName(cons), (void*)sol);
1506
1507 consdata = SCIPconsGetData(cons);
1508 assert(consdata != NULL);
1509 assert(consdata->binvars != NULL || consdata->nbinvars == 0);
1510
1511 /* in case there is only at most one binary variables, the constraints should already be disabled */
1512 assert(consdata->nbinvars > 1);
1513
1514 /* calculate the constraint's activity for the linking part and the set partitioning part */
1515 binvars = consdata->binvars;
1516 vals = consdata->vals;
1517 nbinvars = consdata->nbinvars;
1518
1519 linksum = 0.0;
1520 setpartsum = 0.0;
1521 setpartsumbound = 1.0 + 2*SCIPfeastol(scip);
1522
1523 for( b = 0; b < nbinvars && setpartsum < setpartsumbound; ++b ) /* if sum >= sumbound, the feasibility is clearly decided */
1524 {
1525 assert(SCIPvarIsBinary(binvars[b]));
1526
1527 solval = SCIPgetSolVal(scip, sol, binvars[b]);
1528 assert(SCIPisFeasGE(scip, solval, 0.0) && SCIPisFeasLE(scip, solval, 1.0));
1529
1530 linksum += vals[b] * solval;
1531 setpartsum += solval;
1532 }
1533
1534 /* calculate and update absolute and relative violation of the equality constraint */
1535 linkvarval = SCIPgetSolVal(scip, sol, consdata->linkvar);
1536 absviol = REALABS(linksum - linkvarval);
1537 relviol = REALABS(SCIPrelDiff(linksum, linkvarval));
1538 if( sol != NULL )
1540
1541 /* calculate and update absolute and relative violation of the set partitioning constraint */
1542 absviol = REALABS(setpartsum - 1.0);
1544 if( sol != NULL )
1546
1547 /* check if the fixed binary variable match with the linking variable */
1548 return SCIPisFeasEQ(scip, linksum, linkvarval) && SCIPisFeasEQ(scip, setpartsum, 1.0);
1549}
1550
1551#if 0
1552/** transfer aggregated integer variables to the corresponding binary variables */
1553static
1555 SCIP* scip, /**< SCIP data structure */
1556 SCIP_HASHMAP* varmap, /**< hash map mapping a integer variables to its linking constraint */
1557 SCIP_CONS** conss, /**< array of linking constraint */
1558 int nconss, /**< number of linking constraints */
1559 int* naggrvars, /**< pointer to store the number of aggregate variables */
1560 SCIP_Bool* cutoff /**< pointer to store if a cutoff was detected */
1561 )
1562{
1565 SCIP_CONSDATA* consdata;
1566 SCIP_VAR** binvars;
1568 SCIP_VAR* linkvar;
1570 SCIP_Real aggrconst;
1571 SCIP_Real aggrscalar;
1572 SCIP_Bool infeasible;
1573 SCIP_Bool redundant;
1574 SCIP_Bool aggregated;
1575 int offset;
1576 int aggroffset;
1577 int nbinvars;
1578 int shift;
1579 int b;
1580 int c;
1581
1582 assert(varmap != NULL);
1583
1584 for( c = 0; c < nconss; ++c )
1585 {
1586 consdata = SCIPconsGetData(conss[c]);
1587 assert(consdata != NULL);
1588
1589 linkvar = consdata->linkvar;
1590 assert(linkvar != NULL);
1591
1593 {
1594 aggrvar = SCIPvarGetAggrVar(linkvar);
1596
1597 /* check if the aggregate variable belongs to a linking constraint */
1598 if( aggrcons != NULL )
1599 {
1602
1605
1606 /**@todo extend the aggregation for those cases were the aggrscalar is not equal to 1.0 */
1607 if( SCIPisEQ(scip, aggrscalar, 1.0 ) )
1608 {
1609 /* since both variables are integer variable and the aggrscalar is 1.0 the aggrconst should
1610 * integral
1611 */
1614
1615 offset = consdata->offset;
1616 binvars = consdata->binvars;
1617 aggroffset = aggrconsdata->offset;
1618 aggrbinvars = aggrconsdata->binvars;
1619
1620 nbinvars = MIN(consdata->nbinvars + offset, aggrconsdata->nbinvars + shift + aggroffset);
1621
1622 for( b = MAX(offset, aggroffset-shift); b < nbinvars; ++b )
1623 {
1624 assert(b - offset >= 0);
1625 assert(b + shift - aggroffset >= 0);
1628
1629 /* add aggregation x - y = 0.0 */
1630 SCIP_CALL( SCIPaggregateVars(scip, binvars[b-offset], aggrbinvars[b+shift-aggroffset], 1.0, -1.0, 0.0,
1631 &infeasible, &redundant, &aggregated) );
1632
1633 if( infeasible )
1634 {
1635 (*cutoff) = TRUE;
1636 return SCIP_OKAY;
1637 }
1638
1639 if( aggregated )
1640 (*naggrvars)++;
1641 }
1642 }
1643 }
1644 }
1645 }
1646 return SCIP_OKAY;
1647}
1648#endif
1649
1650/** create two rows for the linking constraint
1651 *
1652 * - row1: {sum_{b=1}^n-1 vals[b] * binvars[b]} - linkvar = 0
1653 * - row2: {sum_{b=0}^n-1 binvars[b]} = 1.0
1654 */
1655static
1657 SCIP* scip, /**< SCIP data structure */
1658 SCIP_CONS* cons /**< linking constraint */
1659 )
1660{
1661 SCIP_CONSDATA* consdata;
1662 char rowname[SCIP_MAXSTRLEN];
1663 int b;
1664
1665 assert( cons != NULL);
1666
1667 /* get constraint data */
1668 consdata = SCIPconsGetData(cons);
1669 assert(consdata != NULL);
1670 assert(consdata->row1 == NULL);
1671 assert(consdata->row2 == NULL);
1672 assert(consdata->nbinvars > 1);
1673
1674 /* create the LP row which captures the linking between the real and binary variables */
1676
1677 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row1, cons, rowname, 0.0, 0.0,
1679
1680 /* add linking variable to the row */
1681 assert(consdata->linkvar != NULL);
1682 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row1, consdata->linkvar, -1.0) );
1683
1684 /* adding binary variables to the row */
1685 assert(consdata->binvars != NULL);
1686 for( b = 0; b < consdata->nbinvars; ++b )
1687 {
1688 SCIP_CALL( SCIPaddVarToRow(scip, consdata->row1, consdata->binvars[b], consdata->vals[b]) );
1689 }
1690
1691 /* create the LP row which captures the set partitioning condition of the binary variables */
1692 (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[setppc]", SCIPconsGetName(cons));
1693 assert( consdata->nbinvars > 0 );
1694
1695 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->row2, cons, rowname, 1.0, 1.0,
1697
1698 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->row2, consdata->nbinvars, consdata->binvars, 1.0) );
1699
1700 return SCIP_OKAY;
1701}
1702
1703
1704/** adds linking constraint as cut to the LP */
1705static
1707 SCIP* scip, /**< SCIP data structure */
1708 SCIP_CONS* cons, /**< linking constraint */
1709 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1710 )
1711{
1712 SCIP_CONSDATA* consdata;
1713
1714 assert( cutoff != NULL );
1715 *cutoff = FALSE;
1716
1717 consdata = SCIPconsGetData(cons);
1718 assert(consdata != NULL);
1719
1720 /* in case there is only at most one binary variables, the constraints should already be disabled */
1721 assert(consdata->nbinvars > 1);
1722
1723 if( consdata->row1 == NULL )
1724 {
1725 assert(consdata->row2 == NULL);
1726
1727 /* convert linking data into LP rows */
1728 SCIP_CALL( createRows(scip, cons) );
1729 }
1730 assert(consdata->row1 != NULL);
1731 assert(consdata->row2 != NULL);
1732
1733 /* insert LP linking row as cut */
1734 if( !SCIProwIsInLP(consdata->row1) )
1735 {
1736 SCIPdebugMsg(scip, "adding linking row of constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
1737 SCIP_CALL( SCIPaddRow(scip, consdata->row1, TRUE/*FALSE*/, cutoff) );
1738 }
1739
1740 /* insert LP set partitioning row as cut */
1741 if( !SCIProwIsInLP(consdata->row2) )
1742 {
1743 SCIPdebugMsg(scip, "adding set partitioning row of constraint <%s> as cut to the LP\n", SCIPconsGetName(cons));
1744 SCIP_CALL( SCIPaddRow(scip, consdata->row2, TRUE/*FALSE*/, cutoff) );
1745 }
1746
1747 return SCIP_OKAY;
1748}
1749
1750/** adds linking constraint as rows to the NLP, if not added yet */
1751static
1753 SCIP* scip, /**< SCIP data structure */
1754 SCIP_CONS* cons /**< linking constraint */
1755 )
1756{
1757 SCIP_CONSDATA* consdata;
1758
1760
1761 /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
1762 if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) )
1763 return SCIP_OKAY;
1764
1765 consdata = SCIPconsGetData(cons);
1766 assert(consdata != NULL);
1767
1768 if( consdata->nlrow1 == NULL )
1769 {
1770 char rowname[SCIP_MAXSTRLEN];
1771 SCIP_Real* coefs;
1772 int i;
1773
1774 assert(consdata->nlrow2 == NULL);
1775
1776 /* create the NLP row which captures the linking between the real and binary variables */
1778
1779 /* create nlrow1 with binary variables */
1780 SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow1, rowname,
1781 0.0, consdata->nbinvars, consdata->binvars, consdata->vals, NULL, 0.0, 0.0, SCIP_EXPRCURV_LINEAR) );
1782 /* add linking variable to the row */
1783 SCIP_CALL( SCIPaddLinearCoefToNlRow(scip, consdata->nlrow1, consdata->linkvar, -1.0) );
1784
1785 /* create the NLP row which captures the set partitioning condition of the binary variables */
1786 (void)SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s[setppc]", SCIPconsGetName(cons));
1787
1788 SCIP_CALL( SCIPallocBufferArray(scip, &coefs, consdata->nbinvars) );
1789 for( i = 0; i < consdata->nbinvars; ++i )
1790 coefs[i] = 1.0;
1791
1792 SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow2, rowname,
1793 0.0, consdata->nbinvars, consdata->binvars, coefs, NULL, 1.0, 1.0, SCIP_EXPRCURV_LINEAR) );
1794
1795 SCIPfreeBufferArray(scip, &coefs);
1796 }
1797
1798 assert(SCIPnlrowIsInNLP(consdata->nlrow1) == SCIPnlrowIsInNLP(consdata->nlrow2));
1799 if( !SCIPnlrowIsInNLP(consdata->nlrow1) )
1800 {
1801 SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow1) );
1802 SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow2) );
1803 }
1804
1805 return SCIP_OKAY;
1806}
1807
1808/** checks constraint for violation, and adds it as a cuts if possible */
1809static
1811 SCIP* scip, /**< SCIP data structure */
1812 SCIP_CONS* cons, /**< linking constraint to be separated */
1813 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1814 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1815 SCIP_Bool* separated, /**< pointer to store TRUE, if a cut was found */
1816 int* nchgbds /**< pointer to store the number of changed variables bounds */
1817 )
1818{
1819 SCIP_CONSDATA* consdata;
1820 SCIP_Bool addcut;
1821 SCIP_Bool mustcheck;
1822
1823 assert(cons != NULL);
1824 assert(SCIPconsGetHdlr(cons) != NULL);
1826 assert(cutoff != NULL);
1827 assert(separated != NULL);
1828 assert(nchgbds != NULL);
1829
1830 consdata = SCIPconsGetData(cons);
1831 assert(consdata != NULL);
1832
1833 /* in case there is only at most one binary variables, the constraints should already be disabled */
1834 assert(consdata->nbinvars > 1);
1835
1836 SCIPdebugMsg(scip, "separating constraint <%s>\n", SCIPconsGetName(cons));
1837
1838 *cutoff = FALSE;
1839 addcut = FALSE;
1840 mustcheck = TRUE;
1841
1842 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
1843 if( sol == NULL )
1844 {
1845 SCIP_CALL( processRealBoundChg(scip, cons, cutoff, nchgbds, &mustcheck) );
1846 }
1847
1848 if( mustcheck && !(*cutoff) )
1849 {
1850 /* variable's fixings didn't give us any information -> we have to check the constraint */
1851 if( sol == NULL && consdata->row1 != NULL )
1852 {
1853 SCIP_Real feasibility;
1854 SCIP_Real tmp;
1855
1856 assert(consdata->row2 != NULL);
1857
1858 /* skip constraints already in the LP */
1859 if( SCIProwIsInLP(consdata->row1) && SCIProwIsInLP(consdata->row2))
1860 return SCIP_OKAY;
1861
1862 feasibility = 1.0;
1863
1864 /* check first row (linking) for feasibility */
1865 if( !SCIProwIsInLP(consdata->row1) )
1866 {
1867 tmp = SCIPgetRowLPFeasibility(scip, consdata->row1);
1869 }
1870
1871 /* check second row (setppc) for feasibility */
1872 if( !SCIProwIsInLP(consdata->row2) )
1873 {
1874 tmp = SCIPgetRowLPFeasibility(scip, consdata->row2);
1876 }
1878 }
1879 else
1880 addcut = !checkCons(scip, cons, sol);
1881
1882 if( !addcut )
1883 {
1884 /* constraint was feasible -> increase age */
1885 SCIP_CALL( SCIPincConsAge(scip, cons) );
1886 }
1887 }
1888
1889 if( addcut )
1890 {
1891 /* insert LP row as cut */
1892 assert(!(*cutoff));
1893 SCIP_CALL( addCuts(scip, cons, cutoff) );
1895 *separated = TRUE;
1896 }
1897
1898 return SCIP_OKAY;
1899}
1900
1901/** enforces the pseudo solution on the given constraint */
1902static
1904 SCIP* scip, /**< SCIP data structure */
1905 SCIP_CONS* cons, /**< linking constraint to be separated */
1906 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1907 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
1908 int* nchgbds, /**< pointer to store the number of changed variable bounds */
1909 SCIP_Bool* solvelp /**< pointer to store TRUE, if the LP has to be solved */
1910 )
1911{
1912 SCIP_Bool addcut;
1913 SCIP_Bool mustcheck;
1914
1916 assert(cons != NULL);
1917 assert(SCIPconsGetHdlr(cons) != NULL);
1919 assert(cutoff != NULL);
1920 assert(infeasible != NULL);
1921 assert(nchgbds != NULL);
1922 assert(solvelp != NULL);
1923
1924 addcut = FALSE;
1925 mustcheck = TRUE;
1926
1927 /* check constraint for violation only looking at the fixed variables, apply further fixings if possible */
1928 SCIP_CALL( processRealBoundChg(scip, cons, cutoff, nchgbds, &mustcheck) );
1929 SCIP_CALL( processBinvarFixings(scip, cons, cutoff, nchgbds, &addcut, &mustcheck) );
1930
1931 if( mustcheck )
1932 {
1933 assert(!addcut);
1934
1935 if( checkCons(scip, cons, NULL) )
1936 {
1937 /* constraint was feasible -> increase age */
1938 SCIP_CALL( SCIPincConsAge(scip, cons) );
1939 }
1940 else
1941 {
1942 /* constraint was infeasible -> reset age */
1944 *infeasible = TRUE;
1945 }
1946 }
1947
1948 if( addcut )
1949 {
1950 assert(!(*cutoff));
1951 /* a cut must be added to the LP -> we have to solve the LP immediately */
1953 *solvelp = TRUE;
1954 }
1955
1956 return SCIP_OKAY;
1957}
1958
1959/** helper function to enforce constraints */
1960static
1962 SCIP* scip, /**< SCIP data structure */
1963 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1964 SCIP_CONS** conss, /**< constraints to process */
1965 int nconss, /**< number of constraints */
1966 int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
1967 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
1968 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
1969 )
1970{
1971 SCIP_Bool cutoff;
1972 SCIP_Bool separated;
1973 int nchgbds;
1974 int c;
1975
1976 assert(conshdlr != NULL);
1978 assert(nconss == 0 || conss != NULL);
1979 assert(result != NULL);
1980
1981 SCIPdebugMsg(scip, "Enforcing %d linking constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation");
1982
1983 cutoff = FALSE;
1984 separated = FALSE;
1985 nchgbds = 0;
1986
1987 /* check all useful linking constraints for feasibility */
1988 for( c = 0; c < nusefulconss && !cutoff && nchgbds == 0; ++c )
1989 {
1990 SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) );
1991 }
1992
1993 /* check all obsolete linking constraints for feasibility */
1994 for( c = nusefulconss; c < nconss && !cutoff && !separated && nchgbds == 0; ++c )
1995 {
1996 SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) );
1997 }
1998
1999 /* return the correct result */
2000 if( cutoff )
2002 else if( nchgbds > 0 )
2004 else if( separated )
2006 else
2008
2009 return SCIP_OKAY;
2010}
2011
2012/*
2013 * Callback methods of constraint handler
2014 */
2015
2016/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2017static
2019{ /*lint --e{715}*/
2020 assert(scip != NULL);
2021 assert(conshdlr != NULL);
2023
2024 /* call inclusion method of constraint handler */
2026
2027 *valid = TRUE;
2028
2029 return SCIP_OKAY;
2030}
2031
2032/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
2033static
2035{
2036 SCIP_CONSHDLRDATA* conshdlrdata;
2037
2038 assert(conshdlr != NULL);
2040 assert(scip != NULL);
2041
2042 /* free constraint handler data */
2043 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2044 assert(conshdlrdata != NULL);
2045
2046 conshdlrdataFree(scip, &conshdlrdata);
2047
2048 return SCIP_OKAY;
2049}
2050
2051
2052/** presolving initialization method of constraint handler (called when presolving is about to begin) */
2053static
2055{ /*lint --e{715}*/
2056 SCIP_CONSHDLRDATA* conshdlrdata;
2057 SCIP_CONSDATA* consdata;
2058 int c;
2059
2060 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2061 assert(conshdlrdata != NULL);
2062
2063 /* disable all linking constraints which contain at most one binary variable */
2064 for( c = 0; c < nconss; ++c )
2065 {
2066 consdata = SCIPconsGetData(conss[c]);
2067 assert(consdata != NULL);
2068
2069 /* skip constraints which are not added */
2070 if( !SCIPconsIsAdded(conss[c]) )
2071 continue;
2072
2073 if( consdata->nbinvars <= 1 )
2074 {
2075 SCIP_CALL( SCIPdisableCons(scip, conss[c]) );
2076 assert(consdata->nbinvars == 0 || SCIPvarGetLbGlobal(consdata->binvars[0]) > 0.5);
2077 }
2078 else if( conshdlrdata->linearize )
2079 {
2080 SCIP_CALL( consdataLinearize(scip, conss[c], consdata) );
2081 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2082 }
2083 }
2084
2085 return SCIP_OKAY;
2086}
2087
2088/** solving process initialization method of constraint handler */
2089static
2091{ /*lint --e{715}*/
2092 /* add nlrow representations to NLP, if NLP had been constructed */
2094 {
2095 int c;
2096 for( c = 0; c < nconss; ++c )
2097 {
2098 SCIP_CALL( addNlrow(scip, conss[c]) );
2099 }
2100 }
2101
2102 return SCIP_OKAY;
2103}
2104
2105/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
2106static
2108{ /*lint --e{715}*/
2109 SCIP_CONSDATA* consdata;
2110 int c;
2111
2112 for( c = 0; c < nconss; ++c )
2113 {
2114 consdata = SCIPconsGetData(conss[c]);
2115 assert(consdata != NULL);
2116
2117 /* release the rows and nlrows of all constraints */
2118 if( consdata->row1 != NULL )
2119 {
2120 assert(consdata->row2 != NULL);
2121
2122 SCIP_CALL( SCIPreleaseRow(scip, &consdata->row1) );
2123 SCIP_CALL( SCIPreleaseRow(scip, &consdata->row2) );
2124 }
2125
2126 if( consdata->nlrow1 != NULL )
2127 {
2128 assert(consdata->nlrow2 != NULL);
2129
2130 SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow1) );
2131 SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow2) );
2132 }
2133 }
2134
2135 return SCIP_OKAY;
2136}
2137
2138
2139/** frees specific constraint data */
2140static
2142{ /*lint --e{715}*/
2143 SCIP_CONSHDLRDATA* conshdlrdata;
2144
2145 assert(conshdlr != NULL);
2147 assert(consdata != NULL);
2148 assert(*consdata != NULL);
2149
2150 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2151 assert(conshdlrdata != NULL);
2152 assert(conshdlrdata->eventhdlr != NULL);
2153
2154 /* remove linking constraint form variable hash map */
2155 assert(conshdlrdata->varmap != NULL);
2156 assert(SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey((*consdata)->linkvar)));
2157 SCIP_CALL( SCIPhashmapRemove(conshdlrdata->varmap, getHashmapKey((*consdata)->linkvar)) );
2158
2159 if( (*consdata)->nbinvars > 0 && SCIPisTransformed(scip) )
2160 {
2161 SCIP_CALL( dropAllEvents(scip, *consdata, conshdlrdata->eventhdlr) );
2162 }
2163
2164 /* free consdata */
2165 SCIP_CALL( consdataFree(scip, consdata) );
2166
2167 return SCIP_OKAY;
2168}
2169
2170
2171/** transforms constraint data into data belonging to the transformed problem */
2172static
2174{ /*lint --e{715}*/
2177 SCIP_CONSHDLRDATA* conshdlrdata;
2178
2179 assert(conshdlr != NULL);
2184
2185 /* free constraint handler data */
2186 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2187 assert(conshdlrdata != NULL);
2188 assert(conshdlrdata->eventhdlr != NULL);
2189
2192 assert(sourcedata->row1 == NULL); /* in original problem, there cannot be LP rows */
2193 assert(sourcedata->row2 == NULL); /* in original problem, there cannot be LP rows */
2194
2195 SCIPdebugMsg(scip, "transform linking constraint for variable <%s>\n", SCIPvarGetName(sourcedata->linkvar));
2196
2197 /* create constraint data for target constraint */
2198 SCIP_CALL( consdataCreate(scip, conshdlrdata->eventhdlr, &targetdata,
2199 sourcedata->linkvar, sourcedata->binvars, sourcedata->vals, sourcedata->nbinvars) );
2200
2201 /* create target constraint */
2207
2208 /* insert (transformed) linking constraint into the hash map */
2209 assert(conshdlrdata->varmap != NULL);
2210 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varmap, getHashmapKey(targetdata->linkvar), *targetcons) );
2211
2212 return SCIP_OKAY;
2213}
2214
2215/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
2216static
2218{ /*lint --e{715}*/
2219 SCIP_CONSDATA* consdata;
2220 int c;
2221
2222 *infeasible = FALSE;
2223
2224 for( c = 0; c < nconss && !(*infeasible); ++c )
2225 {
2226 assert(SCIPconsIsInitial(conss[c]));
2227
2228 consdata = SCIPconsGetData(conss[c]);
2229 assert(consdata != NULL);
2230
2231 if( consdata->nbinvars <= 1 )
2232 continue;
2233
2234 SCIP_CALL( addCuts(scip, conss[c], infeasible) );
2235 }
2236
2237 return SCIP_OKAY;
2238}
2239
2240
2241/** separation method of constraint handler for LP solutions */
2242static
2244{ /*lint --e{715}*/
2245 SCIP_Bool cutoff;
2246 SCIP_Bool separated;
2247 int nchgbds;
2248 int c;
2249
2250 assert(conshdlr != NULL);
2252 assert(nconss == 0 || conss != NULL);
2253 assert(result != NULL);
2254
2255 SCIPdebugMsg(scip, "separating %d/%d linking constraints\n", nusefulconss, nconss);
2256
2257 cutoff = FALSE;
2258 separated = FALSE;
2259 nchgbds = 0;
2260
2261 /* check all useful linking constraints for feasibility */
2262 for( c = 0; c < nusefulconss && !cutoff; ++c )
2263 {
2264 SCIP_CALL( separateCons(scip, conss[c], NULL, &cutoff, &separated, &nchgbds) );
2265 }
2266
2267 /* return the correct result */
2268 if( cutoff )
2270 else if( nchgbds > 0 )
2272 else if( separated )
2274 else
2276
2277 return SCIP_OKAY;
2278}
2279
2280
2281/** separation method of constraint handler for arbitrary primal solutions */
2282static
2284{ /*lint --e{715}*/
2285 SCIP_Bool cutoff;
2286 SCIP_Bool separated;
2287 int nchgbds;
2288 int c;
2289
2290 assert(conshdlr != NULL);
2292 assert(nconss == 0 || conss != NULL);
2293 assert(result != NULL);
2294
2295 SCIPdebugMsg(scip, "separating %d/%d " CONSHDLR_NAME " constraints\n", nusefulconss, nconss);
2296
2297 cutoff = FALSE;
2298 separated = FALSE;
2299 nchgbds = 0;
2300
2301 /* check all useful set partitioning / packing / covering constraints for feasibility */
2302 for( c = 0; c < nusefulconss && !cutoff; ++c )
2303 {
2304 SCIP_CALL( separateCons(scip, conss[c], sol, &cutoff, &separated, &nchgbds) );
2305 }
2306
2307 /* return the correct result */
2308 if( cutoff )
2310 else if( nchgbds > 0 )
2312 else if( separated )
2314 else
2316
2317 return SCIP_OKAY;
2318}
2319
2320
2321/** constraint enforcing method of constraint handler for LP solutions */
2322static
2324{ /*lint --e{715}*/
2325 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, NULL, result) );
2326
2327 return SCIP_OKAY;
2328}
2329
2330
2331/** constraint enforcing method of constraint handler for relaxation solutions */
2332static
2334{ /*lint --e{715}*/
2335 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, nusefulconss, sol, result) );
2336
2337 return SCIP_OKAY;
2338}
2339
2340
2341/** constraint enforcing method of constraint handler for pseudo solutions */
2342static
2344{ /*lint --e{715}*/
2345 SCIP_Bool cutoff;
2346 SCIP_Bool infeasible;
2347 int nchgbds;
2348 SCIP_Bool solvelp;
2349 int c;
2350
2351 assert(conshdlr != NULL);
2353 assert(nconss == 0 || conss != NULL);
2354 assert(result != NULL);
2355
2356 SCIPdebugMsg(scip, "pseudo enforcing %d " CONSHDLR_NAME " constraints\n", nconss);
2357
2358 if( objinfeasible )
2359 {
2361 return SCIP_OKAY;
2362 }
2363
2364 cutoff = FALSE;
2365 infeasible = FALSE;
2366 nchgbds = 0;
2367 solvelp = FALSE;
2368
2369 /* check all linking constraint for domain reductions and feasibility */
2370 for( c = 0; c < nconss && !cutoff && !solvelp; ++c )
2371 {
2372 SCIP_CALL( enforcePseudo(scip, conss[c], &cutoff, &infeasible, &nchgbds, &solvelp) );
2373 }
2374
2375 if( cutoff )
2377 else if( nchgbds > 0 )
2379 else if( solvelp )
2381 else if( infeasible )
2383 else
2385
2386 return SCIP_OKAY;
2387}
2388
2389
2390/** feasibility check method of constraint handler for integral solutions */
2391static
2393{ /*lint --e{715}*/
2394 SCIP_CONS* cons;
2395 SCIP_CONSDATA* consdata;
2396 int c;
2397
2398 assert(conshdlr != NULL);
2400 assert(nconss == 0 || conss != NULL);
2401 assert(result != NULL);
2402
2404
2405 /* check all linking constraints for feasibility */
2406 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
2407 {
2408 cons = conss[c];
2409 consdata = SCIPconsGetData(cons);
2410 assert(consdata != NULL);
2411
2412 if( consdata->nbinvars > 1 && (checklprows || consdata->row1 == NULL || !SCIProwIsInLP(consdata->row1)) )
2413 {
2414 if( !checkCons(scip, cons, sol) )
2415 {
2416 /* constraint is violated */
2418
2419 if( printreason )
2420 {
2421 int pos;
2422 int b;
2423
2424 pos = -1;
2425
2426#ifndef NDEBUG
2427 for( b = 0; b < consdata->nbinvars; ++b )
2428 {
2429 assert(consdata->binvars[b] != NULL);
2430 assert(SCIPvarIsBinary(consdata->binvars[b]));
2431 }
2432#endif
2433
2434 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2435 SCIPinfoMessage(scip, NULL, ";\n");
2436
2437 /* check that at most one binary variable is fixed */
2438 for( b = 0; b < consdata->nbinvars; ++b )
2439 {
2440 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, consdata->binvars[b])) );
2441
2442 /* check if binary variable is fixed */
2443 if( SCIPgetSolVal(scip, sol, consdata->binvars[b]) > 0.5 )
2444 {
2445 if( pos != -1 )
2446 {
2447 SCIPinfoMessage(scip, NULL, "violation: more than one binary variable is set to one");
2448 break;
2449 }
2450 pos = b ;
2451 }
2452 }
2453
2454 /* check that at least one binary variable is fixed */
2455 if( pos == -1 )
2456 {
2457 SCIPinfoMessage(scip, NULL, "violation: none of the binary variables is set to one\n");
2458 }
2459 else if( !SCIPisFeasEQ(scip, consdata->vals[pos], SCIPgetSolVal(scip, sol, consdata->linkvar)) )
2460 {
2461 /* check if the fixed binary variable match with the linking variable */
2462 SCIPinfoMessage(scip, NULL, "violation: <%s> = <%g> and <%s> is one\n",
2463 SCIPvarGetName(consdata->linkvar), SCIPgetSolVal(scip, sol, consdata->linkvar),
2464 SCIPvarGetName(consdata->binvars[pos]) );
2465 }
2466 }
2467 }
2468 }
2469 }
2470
2471 return SCIP_OKAY;
2472}
2473
2474/** domain propagation method of constraint handler */
2475static
2477{ /*lint --e{715}*/
2478 SCIP_Bool cutoff = FALSE;
2479 int nchgbds = 0;
2480 int c;
2481
2482 assert(conshdlr != NULL);
2484 assert(nconss == 0 || conss != NULL);
2485 assert(result != NULL);
2486
2487 SCIPdebugMsg(scip, "propagating %d/%d " CONSHDLR_NAME " constraints\n", nusefulconss, nconss);
2488
2489 /* propagate all useful set partitioning / packing / covering constraints */
2490 for( c = 0; c < nusefulconss && !cutoff; ++c )
2491 {
2492 SCIP_Bool addcut;
2493 SCIP_Bool mustcheck;
2494
2495 SCIP_CALL( processRealBoundChg(scip, conss[c], &cutoff, &nchgbds, &mustcheck) );
2496 SCIP_CALL( processBinvarFixings(scip, conss[c], &cutoff, &nchgbds, &addcut, &mustcheck) );
2497 } /*lint !e438*/
2498
2499 /* return the correct result */
2500 if( cutoff )
2502 else if( nchgbds > 0 )
2504 else
2506
2507 return SCIP_OKAY;
2508}
2509
2510
2511/** presolving method of constraint handler */
2512static
2514{ /*lint --e{715}*/
2515 SCIP_CONSHDLRDATA* conshdlrdata;
2516 int oldnfixedvars;
2517 int oldnchgbds;
2518 int oldnaggrvars;
2519 int oldndelconss;
2520 int firstchange;
2521 int firstclique;
2522 int lastclique;
2523 int c;
2524 SCIP_Bool fixed;
2525 SCIP_Bool cutoff;
2526 SCIP_Bool infeasible;
2527 SCIP_Bool mustcheck;
2528
2529 assert(conshdlr != NULL);
2531 assert(scip != NULL);
2532 assert(result != NULL);
2533
2534 SCIPdebugMsg(scip, "presolve %d linking constraints\n", nconss);
2535
2536 (*result) = SCIP_DIDNOTFIND;
2537
2538 oldnchgbds = *nchgbds;
2539 oldnaggrvars = *naggrvars;
2540 oldnfixedvars = *nfixedvars;
2541 oldndelconss = *ndelconss;
2542 cutoff = FALSE;
2543
2544 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2545 assert(conshdlrdata != NULL);
2546
2547 /* process constraints */
2550 lastclique = -1;
2551
2552 /* check for each linking constraint the set partitioning condition */
2553 for( c = 0; c < nconss && !SCIPisStopped(scip); ++c )
2554 {
2555 SCIP_CONS* cons;
2556 SCIP_CONSDATA* consdata;
2557
2559
2560 cons = conss[c];
2561 assert(cons != NULL);
2563
2564 SCIPdebugMsg(scip, "presolve linking constraints <%s>\n", SCIPconsGetName(cons));
2565
2566 consdata = SCIPconsGetData(cons);
2567 assert(consdata != NULL);
2568
2569 if( !SCIPconsIsEnabled(cons) /* || consdata->nbinvars <= 1 */ )
2570 continue;
2571
2572 /* in case there is only at most one binary variables, the constraints should already be disabled */
2573 assert(consdata->nbinvars > 1);
2574
2575 /*SCIPdebugMsg(scip, "presolving set partitioning / packing / covering constraint <%s>\n", SCIPconsGetName(cons));*/
2576 if( consdata->nfixedones >= 2 )
2577 {
2578 /* at least two variables are fixed to 1:
2579 * - a linking constraint is infeasible due to the set partitioning condition
2580 */
2581 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2583 return SCIP_OKAY;
2584 }
2585
2586 if( consdata->nfixedones == 1 )
2587 {
2588 /* exactly one variable is fixed to 1:
2589 * - all other binary variables must be zero due to the set partitioning condition
2590 * - linking variable has to be fixed to corresponding binary variable which is fixed to one
2591 * - if constraint is not modifiable it can be removed
2592 */
2593 SCIP_VAR* var;
2594 int v;
2595
2596 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> has a binary variable fixed to 1.0\n", SCIPconsGetName(cons));
2597
2598 for( v = 0; v < consdata->nbinvars; ++v )
2599 {
2600 var = consdata->binvars[v];
2601 assert(var != NULL);
2602
2603 if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
2604 {
2605 SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
2606
2607 if( infeasible )
2608 {
2609 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == 0\n",
2611
2613 return SCIP_OKAY;
2614 }
2615 assert(fixed);
2616 (*nfixedvars)++;
2617 }
2618 else if( SCIPvarGetLbGlobal(var) > 0.5 )
2619 {
2620 /* fix linking variable */
2621 assert(SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_LOOSE
2622 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_AGGREGATED
2623 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_COLUMN
2624 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_FIXED
2625 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_NEGATED);
2626 SCIP_CALL( SCIPfixVar(scip, consdata->linkvar, consdata->vals[v], &infeasible, &fixed) );
2627
2628 if( infeasible )
2629 {
2630 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == %g\n",
2631 SCIPconsGetName(cons), SCIPvarGetName(consdata->linkvar), consdata->vals[v]);
2632
2634 return SCIP_OKAY;
2635 }
2636
2637 if( fixed )
2638 (*nfixedvars)++;
2639 }
2640 }
2641
2642 /* now all other variables are fixed to zero:
2643 * the constraint is feasible, and if it's not modifiable, it is redundant
2644 */
2645 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> is redundant\n", SCIPconsGetName(cons));
2646 SCIP_CALL( SCIPdelCons(scip, cons) );
2647 (*ndelconss)++;
2648 continue;
2649 }
2650
2651 if( consdata->nfixedzeros == consdata->nbinvars )
2652 {
2653 /* all variables are fixed to zero:
2654 * - a linking constraint is infeasible due the set partitioning condition
2655 */
2656 assert(consdata->nfixedones == 0);
2657
2658 SCIPdebugMsg(scip, "linking constraint <%s> is infeasible due to set partitioning condition\n", SCIPconsGetName(cons));
2660 return SCIP_OKAY;
2661 }
2662
2663 if( consdata->nfixedzeros == consdata->nbinvars - 1 )
2664 {
2665 /* all variables except one are fixed to zero:
2666 * - a linking constraint is feasible due the set partitioning condition
2667 * - the remaining binary variable can be fixed to one
2668 * - linking variable has to be fixed to corresponding binary variable which is fixed to one
2669 * - constraint can be deleted since it is not modifiable
2670 */
2671 SCIP_VAR* var;
2672 int v;
2673
2674 assert(consdata->nfixedones == 0);
2675
2676 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s> has only one binary variable not fixed to zero\n",
2677 SCIPconsGetName(cons));
2678
2679 /* search unfixed variable */
2680 /* intentional empty for loop to increment counter to proper position */
2681 /* TODO speed up loop by considering only variables between firstnonfixed and lastnonfixed */
2682 for( v = 0; v < consdata->nbinvars && SCIPvarGetUbGlobal(consdata->binvars[v]) < 0.5; ++v ); /*lint !e722*/
2684 var = consdata->binvars[v];
2685
2686 /* fix remaining binary variable */
2687 SCIP_CALL( SCIPfixVar(scip, var, 1.0, &infeasible, &fixed) );
2688 if( infeasible )
2689 {
2690 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == 1\n",
2693 return SCIP_OKAY;
2694 }
2695 assert(fixed);
2696 (*nfixedvars)++;
2697
2698 /* fix linking variable */
2699 assert(SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_LOOSE
2700 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_AGGREGATED
2701 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_COLUMN
2702 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_FIXED
2703 || SCIPvarGetStatus(consdata->linkvar) == SCIP_VARSTATUS_NEGATED);
2704 SCIP_CALL( SCIPfixVar(scip, consdata->linkvar, consdata->vals[v], &infeasible, &fixed) );
2705
2706 if( infeasible )
2707 {
2708 SCIPdebugMsg(scip, CONSHDLR_NAME " constraint <%s>: infeasible fixing <%s> == %g\n",
2709 SCIPconsGetName(cons), SCIPvarGetName(consdata->linkvar), consdata->vals[v]);
2710
2712 return SCIP_OKAY;
2713 }
2714 assert(!SCIPvarIsActive(consdata->linkvar) || fixed);
2715 if( fixed )
2716 (*nfixedvars)++;
2717
2718 /* delete constraint from problem */
2719 SCIP_CALL( SCIPdelCons(scip, cons) );
2720 (*ndelconss)++;
2721 continue;
2722 }
2723
2724 if( consdata->nfixedzeros == consdata->nbinvars - 2 ) /*lint !e641*/
2725 {
2726 SCIP_VAR* var;
2727 SCIP_VAR* var1;
2728 SCIP_VAR* var2;
2729 SCIP_Bool redundant;
2730 SCIP_Bool aggregated;
2731 int v;
2732
2733 /* aggregate variable, if set partitioning condition consists only of two
2734 * non-fixed variables
2735 */
2736
2737 /* search unfixed variable */
2738 var1 = NULL;
2739 var2 = NULL;
2740 for( v = 0; v < consdata->nbinvars && var2 == NULL; ++v )
2741 {
2742 var = consdata->binvars[v];
2743 if( SCIPvarGetUbGlobal(var) > 0.5 )
2744 {
2745 if( var1 == NULL )
2746 var1 = var;
2747 else
2748 var2 = var;
2749 }
2750 }
2751 assert(var1 != NULL && var2 != NULL);
2752
2753 /* aggregate binary equality var1 + var2 == 1 */
2754 SCIPdebugMsg(scip, "" CONSHDLR_NAME " constraint <%s>: aggregate <%s> + <%s> == 1\n",
2756 SCIP_CALL( SCIPaggregateVars(scip, var1, var2, 1.0, 1.0, 1.0, &infeasible, &redundant, &aggregated) );
2757
2758 /* evaluate aggregation result */
2759 if( infeasible )
2760 {
2761 SCIPdebugMsg(scip, "linking constraint <%s>: infeasible aggregation <%s> + <%s> == 1\n",
2764 return SCIP_OKAY;
2765 }
2766 if( aggregated )
2767 (*naggrvars)++;
2768 }
2769
2770 /* apply real bound to binary variables */
2771 SCIP_CALL( processRealBoundChg(scip, cons, &cutoff, nchgbds, &mustcheck) );
2772
2773 /* tightened linking variable */
2774 SCIP_CALL( tightenedLinkvar(scip, cons, consdata, &cutoff, nchgbds) );
2775
2776 /* remove the trailing and leeading binary variable which are fixed to zero */
2777 SCIP_CALL( removeFixedBinvars(scip, conshdlrdata->eventhdlr, cons) );
2778
2779 /* fix the linking variable to the only remaining value and the corresponding binary variable to 1.0 */
2780 if( ! cutoff && consdata->nbinvars == 1 )
2781 {
2782 SCIP_VAR* linkvar;
2783 SCIP_VAR* binvar;
2784 SCIP_Real val;
2785
2786 linkvar = consdata->linkvar;
2787 binvar = consdata->binvars[0];
2788 val = consdata->vals[0];
2789
2790 SCIPdebugMsg(scip, "linking constraint <%s>: fix <%s> to %16.9g as only one binary variable remains",
2791 SCIPconsGetName(cons), SCIPvarGetName(linkvar), val);
2792
2793 SCIP_CALL( SCIPfixVar(scip, binvar, 1.0, &infeasible, &fixed) );
2794 assert(fixed);
2795 ++(*nfixedvars);
2796
2797 if( ! infeasible )
2798 {
2799 SCIP_CALL( SCIPfixVar(scip, linkvar, val, &infeasible, &fixed) );
2800 assert(fixed);
2801 ++(*nfixedvars);
2802 }
2803 cutoff = infeasible;
2804
2805 SCIP_CALL(SCIPdelCons(scip, cons));
2806 ++(*ndelconss);
2807 }
2808
2809 if( cutoff )
2810 {
2812 return SCIP_OKAY;
2813 }
2814
2815 /* remember the first changed constraint to begin the next redundancy round with */
2816 if( firstchange == INT_MAX )
2817 firstchange = c;
2818
2819 /* remember the first and last constraints for which we have to add the clique information */
2820 if( !consdata->cliqueadded && consdata->nbinvars >= 2 )
2821 {
2822 if( firstclique == INT_MAX )
2823 firstclique = c;
2824 lastclique = c;
2825 }
2826 }
2827
2828 /* add clique and implication information */
2829 for( c = firstclique; c < lastclique && !SCIPisStopped(scip); ++c )
2830 {
2831 SCIP_CONS* cons;
2832 SCIP_CONSDATA* consdata;
2833
2835
2836 cons = conss[c];
2837 assert(cons != NULL);
2838
2839 /* ignore deleted constraints */
2840 if( !SCIPconsIsActive(cons) )
2841 continue;
2842
2843 consdata = SCIPconsGetData(cons);
2844 assert(consdata != NULL);
2845
2846 if( !consdata->cliqueadded && consdata->nbinvars >= 3 )
2847 {
2848 /* add set partitioning condition as clique */
2849 int ncliquebdchgs;
2850
2851 SCIP_CALL( SCIPaddClique(scip, consdata->binvars, NULL, consdata->nbinvars, TRUE, &infeasible, &ncliquebdchgs) );
2852 *nchgbds += ncliquebdchgs;
2853
2854 if( infeasible )
2855 {
2857 return SCIP_OKAY;
2858 }
2859
2860 consdata->cliqueadded = TRUE;
2861 }
2862 }
2863
2864#if 0
2865 /* transfer aggregated linking variables to the corresponding binary variables */
2866 assert(conshdlrdata->varmap != NULL);
2867 SCIP_CALL( aggregateVariables(scip, conshdlrdata->varmap, conss, nconss, naggrvars, &cutoff) );
2868#endif
2869
2870 if( cutoff )
2872 else if( oldndelconss < *ndelconss || oldnfixedvars < *nfixedvars || oldnchgbds < *nchgbds || oldnaggrvars < *naggrvars)
2874
2875 return SCIP_OKAY; /*lint !e438*/
2876}
2877
2878
2879/** propagation conflict resolving method of constraint handler */
2880static
2882{ /*lint --e{715}*/
2883 SCIP_CONSDATA* consdata;
2884 SCIP_VAR* linkvar;
2885 int v;
2886
2887 SCIPdebugMsg(scip, "conflict resolving method of " CONSHDLR_NAME " constraint handler\n");
2888
2889 consdata = SCIPconsGetData(cons);
2890 assert(consdata != NULL);
2891
2892 linkvar = consdata->linkvar;
2893 assert(linkvar != NULL);
2894
2896
2897 if( inferinfo == -1 )
2898 {
2899 /* we have to resolve a fixing of a binary variable which was done due to fixed binary variables */
2901 assert(SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)));
2902 assert(SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)));
2903
2904 if( boundtype == SCIP_BOUNDTYPE_UPPER )
2905 {
2906 /* we fixed the binary variable to zero since one of the other binary variable was fixed to one (set
2907 * partitioning condition)
2908 */
2909 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2910
2911 for( v = 0; v < consdata->nbinvars; ++v )
2912 {
2913 if( SCIPgetVarLbAtIndex(scip, consdata->binvars[v], bdchgidx, FALSE) > 0.5 )
2914 {
2915 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[v]) );
2916 break;
2917 }
2918 }
2920 }
2921 else
2922 {
2923 /* we fixed the binary variable to one since all other binary variable were fixed to zero */
2924 assert(boundtype == SCIP_BOUNDTYPE_LOWER);
2925 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
2926
2927 for( v = 0; v < consdata->nbinvars; ++v )
2928 {
2929 if( consdata->binvars[v] != infervar )
2930 {
2931 /* the reason variable must be assigned to zero */
2932 assert(SCIPgetVarUbAtIndex(scip, consdata->binvars[v], bdchgidx, FALSE) < 0.5);
2933 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[v]) );
2934 }
2935 }
2936 }
2937 }
2938 else if( inferinfo == -2 )
2939 {
2940 /* we have to resolve a fixing of a binary variable which was done due to the linking variable lower bound */
2942 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2943 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5); /*@repair: neu*/
2944 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) > 0.5); /*@repair: neu*/
2945 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2946 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2947
2948 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, bdchgidx) );
2949 }
2950 else if( inferinfo == -3 )
2951 {
2952 /* we have to resolve a fixing of a binary variable which was done due to the linking variable upper bound */
2954 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2955 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2956 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, FALSE) > 0.5);
2957 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2958 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
2959
2960 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, bdchgidx) );
2961 }
2962 else if( inferinfo == -4 )
2963 {
2964 SCIP_VAR** binvars;
2965 SCIP_Real* vals;
2966 SCIP_Real lb;
2967 int nbinvars;
2968 int b;
2969
2970 /* we tightened the lower bound of the linking variable due the fixing of the corresponding binary variable to zero */
2971 assert(infervar == linkvar);
2972 assert(boundtype == SCIP_BOUNDTYPE_LOWER);
2973
2974 binvars = consdata->binvars;
2975 nbinvars = consdata->nbinvars;
2976 vals = consdata->vals;
2977
2978 /* get propagated lower bound */
2979 lb = SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE);
2980
2981 for( b = 0; b < nbinvars; ++b )
2982 {
2983 if( vals[b] >= lb )
2984 break;
2985
2986 assert(SCIPvarGetUbLocal(binvars[b]) < 0.5);
2987 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
2988 }
2989 }
2990 else if( inferinfo == -5 )
2991 {
2992 SCIP_VAR** binvars;
2993 SCIP_Real* vals;
2994 SCIP_Real ub;
2995 int nbinvars;
2996 int b;
2997
2998 /* we tightened the upper bound of the linking variable due the fixing of the corresponding binary variable two zero */
2999
3000 assert(infervar == linkvar);
3001 assert(boundtype == SCIP_BOUNDTYPE_UPPER);
3002
3003 binvars = consdata->binvars;
3004 nbinvars = consdata->nbinvars;
3005 vals = consdata->vals;
3006
3007 /* get old and new upper bound */
3008 ub = SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE);
3009
3010 /* resolve tightening of upper bound of the linking variable by binary variables */
3011 for( b = nbinvars - 1; b >= 0; --b )
3012 {
3013 if( vals[b] <= ub )
3014 break;
3015
3016 SCIP_CALL( SCIPaddConflictBinvar(scip, binvars[b]) );
3017 }
3018 }
3019 else if( inferinfo == -6 )
3020 {
3021 /* we fixed a binary variable to one since the linking variable was fixed */
3023 assert(boundtype == SCIP_BOUNDTYPE_LOWER);
3024 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3025 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3026 assert( SCIPisFeasEQ(scip, SCIPgetVarUbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3027 assert( SCIPisFeasEQ(scip, SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, TRUE), SCIPgetVarLbAtIndex(scip, linkvar, bdchgidx, FALSE)) );
3028
3030
3031 SCIP_CALL( SCIPaddConflictLb(scip, linkvar, bdchgidx) );
3032 SCIP_CALL( SCIPaddConflictUb(scip, linkvar, bdchgidx) );
3033 }
3034 else
3035 {
3036 /* we fixed the linking variable to (vals[inferinfo]) since the corresponding binary variable was fixed to one */
3037 assert(infervar == linkvar);
3038 assert(inferinfo >= 0);
3040 assert(SCIPisEQ(scip, consdata->vals[inferinfo], SCIPgetVarUbAtIndex(scip, consdata->linkvar, bdchgidx, TRUE))
3041 || SCIPisEQ(scip, consdata->vals[inferinfo], SCIPgetVarLbAtIndex(scip, consdata->linkvar, bdchgidx, TRUE)));
3042
3043 assert(SCIPgetVarLbAtIndex(scip, consdata->binvars[inferinfo], bdchgidx, FALSE) > 0.5);
3044 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvars[inferinfo]) );
3045 }
3046
3048
3049 return SCIP_OKAY;
3050}
3051
3052/** variable rounding lock method of constraint handler */
3053static
3055{ /*lint --e{715}*/
3056 SCIP_CONSDATA* consdata;
3057 int b;
3058
3060
3061 consdata = SCIPconsGetData(cons);
3062 assert(consdata != NULL);
3063
3064 /* lock linking variable in both directions */
3065 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->linkvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3066
3067 /* look binary variables in both directions */
3068 for( b = 0; b < consdata->nbinvars; ++b )
3069 {
3070 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->binvars[b], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3071 }
3072
3073 return SCIP_OKAY;
3074}
3075
3076/** constraint activation notification method of constraint handler */
3077static
3079{ /*lint --e{715}*/
3080 assert(cons != NULL);
3083
3085 {
3086 SCIP_CALL( addNlrow(scip, cons) );
3087 }
3088
3089 return SCIP_OKAY;
3090}
3091
3092
3093/** constraint deactivation notification method of constraint handler */
3094static
3096{ /*lint --e{715}*/
3097 SCIP_CONSDATA* consdata;
3098
3101
3102 /* get constraint data */
3103 consdata = SCIPconsGetData(cons);
3104 assert(consdata != NULL);
3105
3106 /* remove row from NLP, if still in solving
3107 * if we are in exitsolve, the whole NLP will be freed anyway
3108 */
3109 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow1 != NULL )
3110 {
3111 assert(consdata->nlrow2 != NULL);
3112 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow1) );
3113 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow2) );
3114 }
3115
3116 return SCIP_OKAY;
3117}
3118
3119/** constraint enabling notification method of constraint handler */
3120static
3122{ /*lint --e{715}*/
3123#if 0
3124 SCIP_CONSHDLRDATA* conshdlrdata;
3125 SCIP_CONSDATA* consdata;
3126
3127 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3128 assert(conshdlrdata != NULL);
3129
3130 consdata = SCIPconsGetData(cons);
3131 assert(consdata != NULL);
3132
3133 if( consdata->nbinvars <= 1 )
3134 {
3135 SCIP_CALL( SCIPdisableCons(scip, cons) );
3136 assert(consdata->nbinvars == 0 || SCIPvarGetLbGlobal(consdata->binvars[0]) > 0.5);
3137 }
3138 else if( conshdlrdata->linearize )
3139 {
3140 SCIP_CALL( consdataLinearize(scip, cons, consdata) );
3141 SCIP_CALL( SCIPdelCons(scip, cons) );
3142 }
3143#endif
3144 return SCIP_OKAY;
3145}
3146
3147/** constraint display method of constraint handler */
3148static
3150{ /*lint --e{715}*/
3151 assert(scip != NULL);
3152 assert(conshdlr != NULL);
3153 assert(cons != NULL);
3154
3156
3157 return SCIP_OKAY;
3158}
3159
3160
3161/** constraint copying method of constraint handler */
3162static
3164{ /*lint --e{715}*/
3166 SCIP_VAR** binvars;
3167 SCIP_VAR* linkvar;
3168 SCIP_Real* vals;
3169 const char* consname;
3170 int nbinvars;
3171 int v;
3172
3174 {
3175 SCIPerrorMessage("constraint is not a linking constraint\n");
3176 SCIPABORT();
3177 return SCIP_INVALIDDATA; /*lint !e527*/
3178 }
3179
3180 (*valid) = TRUE;
3181
3184
3185 /* get number of binary variables, linking variables */
3186 nbinvars = sourceconsdata->nbinvars;
3187 linkvar = sourceconsdata->linkvar;
3188
3189 /* duplicate variable array */
3190 if( nbinvars > 0 )
3191 {
3194 }
3195 else
3196 {
3197 binvars = NULL;
3198 vals = NULL;
3199 }
3200
3201 /* get copy for the binary variables */
3202 for( v = 0; v < nbinvars && *valid; ++v )
3203 {
3204 assert(binvars != NULL); /* for flexelint */
3205 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, binvars[v], &binvars[v], varmap, consmap, global, valid) );
3206 assert(!(*valid) || binvars[v] != NULL);
3207 }
3208
3209 /* copy the linking variable */
3210 if( *valid )
3211 {
3212 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, linkvar, &linkvar, varmap, consmap, global, valid) );
3213 assert(!(*valid) || linkvar != NULL);
3214 }
3215
3216 /* only create the target constraint, if all variables could be copied */
3217 if( *valid )
3218 {
3219 if( name != NULL )
3220 consname = name;
3221 else
3222 consname = SCIPconsGetName(sourcecons);
3223
3224 SCIP_CALL( SCIPcreateConsLinking(scip, cons, consname, linkvar, binvars, vals, nbinvars,
3225 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3226 }
3227
3228 /* free buffer array */
3229 if( nbinvars > 0 )
3230 {
3232 SCIPfreeBufferArrayNull(scip, &binvars);
3233 }
3234
3235 return SCIP_OKAY;
3236}
3237
3238/** constraint parsing method of constraint handler */
3239static
3241{ /*lint --e{715}*/
3242 SCIP_VAR** binvars;
3243 SCIP_VAR* linkvar;
3244 SCIP_Real* vals;
3245 char* endptr;
3246 int varssize;
3247 int nbinvars;
3248
3249 assert(scip != NULL);
3250 assert(success != NULL);
3251 assert(str != NULL);
3252 assert(name != NULL);
3253 assert(cons != NULL);
3254
3255 *success = TRUE;
3256
3257 /* parse linking variable */
3258 SCIP_CALL( SCIPparseVarName(scip, str, &linkvar, &endptr) );
3259
3260 if( linkvar == NULL )
3261 {
3262 SCIPerrorMessage("unknown variable name at '%s'\n", str);
3263 *success = FALSE;
3264 return SCIP_OKAY;
3265 }
3266
3267 /* find "==" */
3268 endptr = strchr(endptr, '=');
3269
3270 /* if the string end has been reached without finding the "==" */
3271 if( endptr == NULL )
3272 {
3273 SCIPerrorMessage("Could not find initializing '='.\n");
3274 *success = FALSE;
3275 return SCIP_OKAY;
3276 }
3277
3278 str = endptr;
3279
3280 /* skip "==" */
3281 str += *(str+1) == '=' ? 2 : 1;
3282
3283 /* skip whitespace */
3284 SCIP_CALL( SCIPskipSpace((char**)&str) );
3285
3286 nbinvars = 0;
3287 varssize = 16;
3288 SCIP_CALL( SCIPallocBufferArray(scip, &binvars, varssize) );
3289 SCIP_CALL( SCIPallocBufferArray(scip, &vals, varssize) );
3290
3291 /* check for the string "no binary variables yet" */
3292 if( strncmp(str, "no binary variables yet", 24) != 0 )
3293 {
3294 int requsize;
3295 int v;
3296
3297 /* parse linear sum to get variables and coefficients */
3298 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, binvars, vals, &nbinvars, varssize, &requsize, &endptr, success) );
3299
3300 if( *success && requsize > varssize )
3301 {
3302 /* realloc buffers and try again */
3303 varssize = requsize;
3304 SCIP_CALL( SCIPreallocBufferArray(scip, &binvars, varssize) );
3305 SCIP_CALL( SCIPreallocBufferArray(scip, &vals, varssize) );
3306
3307 SCIP_CALL( SCIPparseVarsLinearsum(scip, str, binvars, vals, &nbinvars, varssize, &requsize, &endptr, success) );
3308 assert(!*success || requsize <= varssize); /* if successful, then should have had enough space now */
3309 }
3310
3311 /* check coefficients */
3312 if( *success )
3313 {
3314 /* convert SCIP_Real to integer */
3315 for( v = 0; v < nbinvars; ++v )
3316 {
3317 if( SCIPisIntegral(scip, vals[v]) )
3318 vals[v] = SCIPconvertRealToInt(scip, vals[v]);
3319 }
3320 }
3321 }
3322
3323 if( *success )
3324 {
3325 SCIP_CALL( SCIPcreateConsLinking(scip, cons, name, linkvar, binvars, vals, nbinvars,
3326 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3327 }
3328
3329 SCIPfreeBufferArray(scip, &vals);
3330 SCIPfreeBufferArray(scip, &binvars);
3331
3332 return SCIP_OKAY;
3333}
3334
3335/** constraint method of constraint handler which returns the variables (if possible) */
3336static
3338{ /*lint --e{715}*/
3339 SCIP_CONSDATA* consdata;
3340
3341 consdata = SCIPconsGetData(cons);
3342 assert(consdata != NULL);
3343
3345 (*success) = FALSE;
3346 else
3347 {
3348 assert(vars != NULL);
3349
3350 BMScopyMemoryArray(vars, consdata->binvars, consdata->nbinvars);
3351 vars[consdata->nbinvars] = consdata->linkvar;
3352 (*success) = TRUE;
3353 }
3354
3355 return SCIP_OKAY;
3356}
3357
3358/** constraint method of constraint handler which returns the number of variables (if possible) */
3359static
3361{ /*lint --e{715}*/
3362 SCIP_CONSDATA* consdata;
3363
3364 consdata = SCIPconsGetData(cons);
3365 assert(consdata != NULL);
3366
3367 (*nvars) = consdata->nbinvars + 1;
3368 (*success) = TRUE;
3369
3370 return SCIP_OKAY;
3371}
3372
3373/*
3374 * Callback methods of event handler
3375 */
3376
3377/** execution method of event handler */
3378static
3380{ /*lint --e{715}*/
3381 SCIP_CONSDATA* consdata;
3382 SCIP_EVENTTYPE eventtype;
3383
3384 assert(eventhdlr != NULL);
3385 assert(eventdata != NULL);
3387 assert(event != NULL);
3388
3389 consdata = (SCIP_CONSDATA*)eventdata;
3390 assert(consdata != NULL);
3391
3392 eventtype = SCIPeventGetType(event);
3393 switch( eventtype )
3394 {
3396 consdata->nfixedones++;
3397 break;
3399 consdata->nfixedones--;
3400 consdata->firstnonfixed = 0;
3401 consdata->lastnonfixed = consdata->nbinvars - 1;
3402 break;
3404 consdata->nfixedzeros++;
3405 break;
3407 consdata->firstnonfixed = 0;
3408 consdata->lastnonfixed = consdata->nbinvars - 1;
3409 consdata->nfixedzeros--;
3410 break;
3411 default:
3412 SCIPerrorMessage("invalid event type\n");
3413 return SCIP_INVALIDDATA;
3414 }
3415 assert(0 <= consdata->nfixedzeros && consdata->nfixedzeros <= consdata->nbinvars);
3416 assert(0 <= consdata->nfixedones && consdata->nfixedones <= consdata->nbinvars);
3417
3418 /*debugMsg(scip, " -> constraint has %d zero-fixed and %d one-fixed of %d variables\n",
3419 consdata->nfixedzeros, consdata->nfixedones, consdata->nvars);*/
3420
3421 return SCIP_OKAY;
3422}
3423
3424/*
3425 * constraint specific interface methods
3426 */
3427
3428/** creates the handler for linking constraints and includes it in SCIP */
3430 SCIP* scip /**< SCIP data structure */
3431 )
3432{
3433 SCIP_CONSHDLRDATA* conshdlrdata;
3434 SCIP_CONSHDLR* conshdlr;
3435 SCIP_EVENTHDLR* eventhdlr;
3436
3437 /* create event handler for bound change events */
3440
3441 /* create linking constraint handler data */
3442 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
3443
3444 /* include constraint handler */
3448 conshdlrdata) );
3449
3450 assert(conshdlr != NULL);
3451
3452 /* set non-fundamental callbacks via specific setter functions */
3475
3476 /* include the linear constraint to linking constraint upgrade in the linear constraint handler */
3477 /* SCIP_CALL( SCIPincludeLinconsUpgrade(scip, linconsUpgdLinking, LINCONSUPGD_PRIORITY, CONSHDLR_NAME) ); */
3478
3479 /* add linking constraint handler parameters */
3481 "constraints/" CONSHDLR_NAME "/linearize", "this constraint will not propagate or separate, linear and setppc are used?",
3482 &conshdlrdata->linearize, FALSE, DEFAULT_LINEARIZE, NULL, NULL) );
3483
3484 return SCIP_OKAY;
3485}
3486
3487/** creates and captures a linking constraint
3488 *
3489 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3490 */
3492 SCIP* scip, /**< SCIP data structure */
3493 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3494 const char* name, /**< name of constraint */
3495 SCIP_VAR* linkvar, /**< linking variable (continuous or integer) which should be linked */
3496 SCIP_VAR** binvars, /**< binary variables */
3497 SCIP_Real* vals, /**< coefficients of the binary variables */
3498 int nbinvars, /**< number of binary starting variables */
3499 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3500 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3501 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3502 * Usually set to TRUE. */
3503 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3504 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3505 SCIP_Bool check, /**< should the constraint be checked for feasibility?
3506 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3507 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3508 * Usually set to TRUE. */
3509 SCIP_Bool local, /**< is constraint only valid locally?
3510 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3511 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3512 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3513 * adds coefficients to this constraint. */
3514 SCIP_Bool dynamic, /**< is constraint subject to aging?
3515 * Usually set to FALSE. Set to TRUE for own cuts which
3516 * are separated as constraints. */
3517 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3518 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3519 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3520 * if it may be moved to a more global node?
3521 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3522 )
3523{
3524 SCIP_CONSHDLR* conshdlr;
3525 SCIP_CONSDATA* consdata;
3526 SCIP_CONSHDLRDATA* conshdlrdata;
3527 int k;
3528
3529 assert(scip != NULL);
3532
3533 /* find the linking constraint handler */
3534 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3535 if( conshdlr == NULL )
3536 {
3537 SCIPerrorMessage("linking constraint handler not found\n");
3538 return SCIP_PLUGINNOTFOUND;
3539 }
3540
3541 SCIPdebugMsg(scip, "create linking constraint for variable <%s> with %d binary variables (SCIP stage %d)\n",
3543 for( k = 0; k < nbinvars; k++ )
3544 {
3545 SCIPdebugMsg(scip, "Var %d : <%s>\n", k, SCIPvarGetName(binvars[k]));
3546 }
3547
3548 /* get constraint handler data */
3549 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3550 assert(conshdlrdata != NULL);
3551
3552 if( conshdlrdata->varmap == NULL )
3553 {
3554 SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varmap, SCIPblkmem(scip), HASHSIZE_BINVARSCONS) );
3555 }
3556 assert(conshdlrdata->varmap != NULL);
3557
3558 /* check if the linking for the requests linking variable already exists */
3559 assert(!SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar)));
3560
3561 /* create the constraint specific data */
3562 SCIP_CALL( consdataCreate(scip, conshdlrdata->eventhdlr, &consdata, linkvar, binvars, vals, nbinvars) );
3563
3564 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata,
3565 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3566
3567 /* create binary variables for the real domain */
3568 if( nbinvars == 0 )
3569 {
3570 SCIP_CALL( consdataCreateBinvars(scip, *cons, consdata, conshdlrdata->eventhdlr, conshdlrdata->linearize) );
3571 }
3572
3573 /* insert linking constraint into the hash map */
3574 SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varmap, getHashmapKey(linkvar), *cons) );
3575 assert(SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar)));
3576
3577 return SCIP_OKAY;
3578}
3579
3580/** creates and captures a linking constraint
3581 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
3582 * method SCIPcreateConsLinking(); all flags can be set via SCIPsetCons<Flagname>-methods in scip.h
3583 *
3584 * @see SCIPcreateConsLinking() for information about the basic constraint flag configuration
3585 *
3586 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3587 */
3589 SCIP* scip, /**< SCIP data structure */
3590 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3591 const char* name, /**< name of constraint */
3592 SCIP_VAR* linkvar, /**< linking variable (continuous or integer) which should be linked */
3593 SCIP_VAR** binvars, /**< binary variables, or NULL */
3594 SCIP_Real* vals, /**< coefficients of the binary variables */
3595 int nbinvars /**< number of binary variables */
3596 )
3597{
3598 assert(scip != NULL);
3599
3600 SCIP_CALL( SCIPcreateConsLinking(scip, cons, name, linkvar, binvars, vals, nbinvars,
3602
3603 return SCIP_OKAY;
3604}
3605
3606/** checks if for the given linking variable (continuous or integer) a linking constraint exists */
3608 SCIP* scip, /**< SCIP data structure */
3609 SCIP_VAR* linkvar /**< linking variable (continuous or integer) which should be linked */
3610 )
3611{
3612 SCIP_CONSHDLR* conshdlr;
3613 SCIP_CONSHDLRDATA* conshdlrdata;
3614
3615 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3616 assert(conshdlr != NULL);
3617
3618 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3619 assert(conshdlrdata != NULL);
3620
3621 return (conshdlrdata->varmap != NULL) && SCIPhashmapExists(conshdlrdata->varmap, getHashmapKey(linkvar));
3622}
3623
3624/** returns the linking constraint belonging the given linking variable (continuous or integer) or NULL if it does not exist yet */
3626 SCIP* scip, /**< SCIP data structure */
3627 SCIP_VAR* linkvar /**< linking variable (continuous or integer) which should be linked */
3628 )
3629{
3630 SCIP_CONSHDLR* conshdlr;
3631 SCIP_CONSHDLRDATA* conshdlrdata;
3632
3633 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3634 assert(conshdlr != NULL);
3635
3636 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3637 assert(conshdlrdata != NULL);
3638
3639 if( conshdlrdata->varmap != NULL )
3640 return (SCIP_CONS*) SCIPhashmapGetImage(conshdlrdata->varmap, getHashmapKey(linkvar));
3641 else
3642 return NULL;
3643}
3644
3645/** returns the linking variable (continuous or integer) of the linking constraint */
3647 SCIP* scip, /**< SCIP data structure */
3648 SCIP_CONS* cons /**< linking constraint */
3649 )
3650{
3651 SCIP_CONSDATA* consdata;
3652
3653 assert(scip != NULL);
3654
3656 {
3657 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3658 SCIPABORT();
3659 return NULL; /*lint !e527*/
3660 }
3661
3662 consdata = SCIPconsGetData(cons);
3663 assert(consdata != NULL);
3664
3665 return consdata->linkvar;
3666}
3667
3668/** returns the binary variables of the linking constraint */
3670 SCIP* scip, /**< SCIP data structure */
3671 SCIP_CONS* cons, /**< linking constraint */
3672 SCIP_VAR*** binvars, /**< pointer to store the binary variables array pointer */
3673 int* nbinvars /**< pointer to store the number of returned binary variables */
3674 )
3675{
3676 SCIP_CONSDATA* consdata;
3677
3678 assert(scip != NULL);
3679
3681 {
3682 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3683 SCIPABORT();
3684 return SCIP_INVALIDDATA; /*lint !e527*/
3685 }
3686
3687 consdata = SCIPconsGetData(cons);
3688 assert(consdata != NULL);
3689
3690 if( consdata->binvars == NULL )
3691 {
3692 SCIP_CONSHDLR* conshdlr;
3693 SCIP_CONSHDLRDATA* conshdlrdata;
3694
3695 conshdlr = SCIPconsGetHdlr(cons);
3696 assert(conshdlr != NULL);
3697
3698 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3699 assert(conshdlrdata != NULL);
3700
3701 SCIP_CALL( consdataCreateBinvars(scip, cons, consdata, conshdlrdata->eventhdlr, conshdlrdata->linearize) );
3702 }
3703
3704 assert(consdata->binvars != NULL);
3705
3706 if( binvars != NULL )
3707 (*binvars) = consdata->binvars;
3708 if( nbinvars != NULL )
3709 (*nbinvars) = consdata->nbinvars;
3710
3711 return SCIP_OKAY;
3712}
3713
3714/** returns the number of binary variables of the linking constraint */
3716 SCIP* scip, /**< SCIP data structure */
3717 SCIP_CONS* cons /**< linking constraint */
3718 )
3719{
3720 SCIP_CONSDATA* consdata;
3721
3722 assert(scip != NULL);
3723
3725 {
3726 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3727 SCIPABORT();
3728 return -1; /*lint !e527*/
3729 }
3730
3731 consdata = SCIPconsGetData(cons);
3732 assert(consdata != NULL);
3733
3734 return consdata->nbinvars;
3735}
3736
3737/** returns the coefficients of the binary variables */
3739 SCIP* scip, /**< SCIP data structure */
3740 SCIP_CONS* cons /**< linking constraint */
3741 )
3742{
3743 SCIP_CONSDATA* consdata;
3744
3745 assert(scip != NULL);
3746
3748 {
3749 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3750 SCIPABORT();
3751 return NULL; /*lint !e527*/
3752 }
3753
3754 consdata = SCIPconsGetData(cons);
3755 assert(consdata != NULL);
3756 consdataSort(consdata);
3757
3758 return consdata->vals;
3759}
3760
3761/** return all binary variable information of the linking constraint */
3763 SCIP_CONS* cons, /**< linking constraint */
3764 SCIP_VAR*** binvars, /**< pointer to store binary variables, or NULL */
3765 SCIP_Real** vals, /**< pointer to store the binary coefficients, or NULL */
3766 int* nbinvars /**< pointer to store the number of binary variables, or NULL */
3767 )
3768{
3769 SCIP_CONSDATA* consdata;
3770
3772 {
3773 SCIPerrorMessage("constraint is not a " CONSHDLR_NAME " constraint\n");
3774 SCIPABORT();
3775 return SCIP_ERROR;
3776 }
3777
3778 consdata = SCIPconsGetData(cons);
3779 assert(consdata != NULL);
3780
3781 consdataSort(consdata);
3782
3783 if( binvars != NULL )
3784 *binvars = consdata->binvars;
3785 if( vals != NULL )
3786 *vals = consdata->vals;
3787 if( nbinvars != NULL )
3788 *nbinvars = consdata->nbinvars;
3789
3790 return SCIP_OKAY;
3791}
SCIP_VAR ** b
static SCIP_RETCODE aggregateVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars)
Constraint handler for linear constraints in their most general form, .
static SCIP_RETCODE consdataLinearize(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata)
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *linkvar, SCIP_VAR *binvar, SCIP_Bool lblinkvar, SCIP_Bool ublinkvar)
static SCIP_RETCODE enforcePseudo(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, SCIP_Bool *infeasible, int *nchgbds, SCIP_Bool *solvelp)
#define CONSHDLR_CHECKPRIORITY
static SCIP_RETCODE addCuts(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff)
#define CONSHDLR_DESC
static SCIP_RETCODE catchAllEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE consFixLinkvar(SCIP *scip, SCIP_CONS *cons, int pos, SCIP_Bool *cutoff)
static SCIP_RETCODE dropEvent(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
static SCIP_RETCODE dropAllEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE removeFixedBinvars(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons)
#define CONSHDLR_PROP_TIMING
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
static SCIP_RETCODE processBinvarFixings(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nchgbds, SCIP_Bool *addcut, SCIP_Bool *mustcheck)
static void * getHashmapKey(SCIP_VAR *var)
#define CONSHDLR_MAXPREROUNDS
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **binvars, int nbinvars)
static SCIP_Bool checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
#define CONSHDLR_SEPAPRIORITY
#define DEFAULT_LINEARIZE
static SCIP_RETCODE catchEvent(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos)
static SCIP_RETCODE processRealBoundChg(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nchgbds, SCIP_Bool *mustcheck)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONSDATA **consdata, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars)
static SCIP_RETCODE consdataCreateBinvars(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool linearize)
static SCIP_RETCODE tightenedLinkvar(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *cutoff, int *nchgbds)
#define CONSHDLR_PROPFREQ
static SCIP_RETCODE createRows(SCIP *scip, SCIP_CONS *cons)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_EVENTHDLR *eventhdlr, SCIP_CONS *cons, int pos)
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
static void consdataSort(SCIP_CONSDATA *consdata)
static SCIP_RETCODE addNlrow(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *cutoff, SCIP_Bool *separated, int *nchgbds)
#define CONSHDLR_EAGERFREQ
#define EVENTHDLR_DESC
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
#define CONSHDLR_ENFOPRIORITY
#define CONSHDLR_DELAYSEPA
#define HASHSIZE_BINVARSCONS
#define CONSHDLR_NAME
#define EVENTHDLR_NAME
#define CONSHDLR_DELAYPROP
constraint handler for linking binary variables to a linking (continuous or integer) variable
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIP_MAXSTRLEN
Definition def.h:302
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
int SCIPgetNBinvarsLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetBinvarsLinking(SCIP *scip, SCIP_CONS *cons, SCIP_VAR ***binvars, int *nbinvars)
SCIP_Bool SCIPexistsConsLinking(SCIP *scip, SCIP_VAR *linkvar)
SCIP_VAR * SCIPgetLinkvarLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_CONS * SCIPgetConsLinking(SCIP *scip, SCIP_VAR *linkvar)
SCIP_RETCODE SCIPcreateConsLinking(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars, 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 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_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, 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 SCIPcreateConsBasicLinking(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *linkvar, SCIP_VAR **binvars, SCIP_Real *vals, int nbinvars)
SCIP_Real * SCIPgetValsLinking(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPgetBinvarsDataLinking(SCIP_CONS *cons, SCIP_VAR ***binvars, SCIP_Real **vals, int *nbinvars)
SCIP_RETCODE SCIPincludeConshdlrLinking(SCIP *scip)
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition scip_copy.c:711
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1668
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:2843
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition misc.c:3058
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3211
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition misc.c:3106
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition misc.c:3024
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3373
SCIP_RETCODE SCIPhashmapRemove(SCIP_HASHMAP *hashmap, void *origin)
Definition misc.c:3389
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3474
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition misc.c:11096
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_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:366
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:664
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition scip_cons.c:534
SCIP_RETCODE SCIPsetConshdlrEnable(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:710
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:486
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition scip_cons.c:229
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition scip_cons.c:275
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:317
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition scip_cons.c:175
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:802
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:825
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:779
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4180
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
Definition scip_cons.c:341
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:886
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:572
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:438
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:687
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4200
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:595
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:641
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:462
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:618
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:848
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition cons.c:8118
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8347
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8108
SCIP_RETCODE SCIPenableCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1783
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8257
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition scip_cons.c:2482
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8287
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition cons.c:8397
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8277
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition cons.c:8149
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition scip_cons.c:943
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8307
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8327
SCIP_Bool SCIPconsIsEnabled(SCIP_CONS *cons)
Definition cons.c:8185
SCIP_RETCODE SCIPdisableCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1817
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8088
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1758
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8337
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition cons.c:8517
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8367
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8267
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1730
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8357
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_Bool SCIPhasCurrentNodeLP(SCIP *scip)
Definition scip_lp.c:83
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
#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 SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_RETCODE SCIPdelNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition scip_nlp.c:391
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition scip_nlp.c:363
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition scip_nlp.c:110
SCIP_RETCODE SCIPaddLinearCoefToNlRow(SCIP *scip, SCIP_NLROW *nlrow, SCIP_VAR *var, SCIP_Real val)
Definition scip_nlp.c:1116
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
Definition scip_nlp.c:1025
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
Definition nlp.c:1872
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
Definition scip_nlp.c:921
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition scip_lp.c:1773
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 SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
SCIP_Real SCIPgetRowLPFeasibility(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:2010
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition lp.c:17523
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
void SCIPupdateSolLPConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition scip_sol.c:285
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPconvertRealToInt(SCIP *scip, SCIP_Real real)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition scip_tree.c:146
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:4351
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:17570
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:17421
SCIP_RETCODE SCIPaddClique(SCIP *scip, SCIP_VAR **vars, SCIP_Bool *values, int nvars, SCIP_Bool isequation, SCIP_Bool *infeasible, int *nbdchgs)
Definition scip_var.c:6921
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition scip_var.c:1480
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
Definition var.c:17656
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition var.c:17383
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition scip_var.c:8401
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5615
SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
Definition var.c:17644
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition var.c:12207
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition scip_var.c:533
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition var.c:17406
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:17910
int SCIPvarGetIndex(SCIP_VAR *var)
Definition var.c:17580
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
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:2128
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1248
SCIP_RETCODE SCIPparseVarsLinearsum(SCIP *scip, const char *str, SCIP_VAR **vars, SCIP_Real *vals, int *nvars, int varssize, int *requiredsize, char **endptr, SCIP_Bool *success)
Definition scip_var.c:704
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition scip_var.c:114
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:17900
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8276
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5501
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:1992
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5723
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition scip_var.c:230
SCIP_RETCODE SCIPwriteVarsLinearsum(SCIP *scip, FILE *file, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Bool type)
Definition scip_var.c:343
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition scip_var.c:1439
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1214
SCIP_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
Definition var.c:17632
void SCIPsortRealPtr(SCIP_Real *realarray, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
SCIP_RETCODE SCIPskipSpace(char **s)
Definition misc.c:10777
return SCIP_OKAY
int c
SCIP_Bool cutoff
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_Bool propagate
static SCIP_VAR ** vars
int nbinvars
#define NULL
Definition lpi_spx1.cpp:161
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition memory.h:136
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition scip_mem.c:57
public methods for managing constraints
public methods for managing events
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition pub_message.h:64
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
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 nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for the branch-and-bound tree
public methods for SCIP variables
#define MAX(x, y)
Definition tclique_def.h:92
@ SCIP_CONFTYPE_PROPAGATION
#define SCIP_DECL_CONSENFOLP(x)
Definition type_cons.h:362
#define SCIP_DECL_CONSINITPRE(x)
Definition type_cons.h:155
#define SCIP_DECL_CONSDELETE(x)
Definition type_cons.h:228
#define SCIP_DECL_CONSGETVARS(x)
Definition type_cons.h:865
#define SCIP_DECL_CONSINITSOL(x)
Definition type_cons.h:200
#define SCIP_DECL_CONSPRINT(x)
Definition type_cons.h:767
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition type_cons.h:64
#define SCIP_DECL_CONSSEPALP(x)
Definition type_cons.h:287
#define SCIP_DECL_CONSENFORELAX(x)
Definition type_cons.h:387
#define SCIP_DECL_CONSPROP(x)
Definition type_cons.h:504
#define SCIP_DECL_CONSGETNVARS(x)
Definition type_cons.h:883
#define SCIP_DECL_CONSRESPROP(x)
Definition type_cons.h:610
#define SCIP_DECL_CONSACTIVE(x)
Definition type_cons.h:689
#define SCIP_DECL_CONSENFOPS(x)
Definition type_cons.h:430
#define SCIP_DECL_CONSPARSE(x)
Definition type_cons.h:843
#define SCIP_DECL_CONSTRANS(x)
Definition type_cons.h:238
#define SCIP_DECL_CONSDEACTIVE(x)
Definition type_cons.h:704
#define SCIP_DECL_CONSPRESOL(x)
Definition type_cons.h:559
#define SCIP_DECL_CONSENABLE(x)
Definition type_cons.h:719
#define SCIP_DECL_CONSINITLP(x)
Definition type_cons.h:258
#define SCIP_DECL_CONSLOCK(x)
Definition type_cons.h:674
#define SCIP_DECL_CONSCOPY(x)
Definition type_cons.h:808
struct SCIP_ConsData SCIP_CONSDATA
Definition type_cons.h:65
#define SCIP_DECL_CONSCHECK(x)
Definition type_cons.h:473
#define SCIP_DECL_CONSHDLRCOPY(x)
Definition type_cons.h:107
#define SCIP_DECL_CONSEXITSOL(x)
Definition type_cons.h:215
#define SCIP_DECL_CONSFREE(x)
Definition type_cons.h:115
#define SCIP_DECL_CONSSEPASOL(x)
Definition type_cons.h:319
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition type_event.h:125
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition type_event.h:79
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#define SCIP_EVENTTYPE_LBRELAXED
Definition type_event.h:78
uint64_t SCIP_EVENTTYPE
Definition type_event.h:151
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition type_event.h:77
#define SCIP_EVENTTYPE_UBRELAXED
Definition type_event.h:80
@ SCIP_EXPRCURV_LINEAR
Definition type_expr.h:62
@ SCIP_BOUNDTYPE_UPPER
Definition type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition type_lp.h:56
@ 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_SEPARATED
Definition type_result.h:49
@ SCIP_SOLVELP
Definition type_result.h:55
@ SCIP_SUCCESS
Definition type_result.h:58
@ SCIP_INFEASIBLE
Definition type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
@ SCIP_INVALIDDATA
@ SCIP_PLUGINNOTFOUND
@ SCIP_ERROR
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_PRESOLVING
Definition type_set.h:49
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
@ SCIP_STAGE_TRANSFORMING
Definition type_set.h:46
@ SCIP_VARTYPE_CONTINUOUS
Definition type_var.h:71
@ SCIP_VARTYPE_BINARY
Definition type_var.h:62
@ SCIP_VARSTATUS_FIXED
Definition type_var.h:52
@ SCIP_VARSTATUS_COLUMN
Definition type_var.h:51
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:54
@ SCIP_VARSTATUS_NEGATED
Definition type_var.h:55
@ SCIP_VARSTATUS_AGGREGATED
Definition type_var.h:53
@ SCIP_VARSTATUS_LOOSE
Definition type_var.h:50
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97