Scippy

SCIP

Solving Constraint Integer Programs

cons_bounddisjunction.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-2025 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_bounddisjunction.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief constraint handler for bound disjunction constraints \f$(x_1 \{\leq,\geq\} b_1) \vee \ldots \vee (x_n \{\leq,\geq\} b_n)\f$
28 * @author Tobias Achterberg
29 * @author Marc Pfetsch
30 */
31
32/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33
36#include "scip/cons_linear.h"
37#include "scip/cons_logicor.h"
38#include "scip/cons_setppc.h"
39#include "scip/expr_pow.h"
40#include "scip/expr_var.h"
41#include "scip/pub_conflict.h"
42#include "scip/pub_cons.h"
43#include "scip/pub_event.h"
44#include "scip/pub_lp.h"
45#include "scip/pub_message.h"
46#include "scip/pub_misc.h"
47#include "scip/pub_var.h"
48#include "scip/scip_branch.h"
49#include "scip/scip_conflict.h"
50#include "scip/scip_cons.h"
51#include "scip/scip_copy.h"
52#include "scip/scip_event.h"
53#include "scip/scip_expr.h"
54#include "scip/scip_general.h"
55#include "scip/scip_mem.h"
56#include "scip/scip_message.h"
57#include "scip/scip_nlp.h"
58#include "scip/scip_numerics.h"
59#include "scip/scip_param.h"
60#include "scip/scip_prob.h"
61#include "scip/scip_probing.h"
62#include "scip/scip_sol.h"
64#include "scip/scip_tree.h"
65#include "scip/scip_var.h"
66#include "scip/symmetry_graph.h"
68#include <string.h>
69
70/**@name Constraint handler properties
71 *
72 * @{
73 */
74#define CONSHDLR_NAME "bounddisjunction"
75#define CONSHDLR_DESC "bound disjunction constraints"
76#define CONSHDLR_ENFOPRIORITY -3000000 /**< priority of the constraint handler for constraint enforcing */
77#define CONSHDLR_CHECKPRIORITY -3000000 /**< priority of the constraint handler for checking feasibility */
78#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
79#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
80 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
81#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
82#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
83#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
84
85#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
86#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
87
88/**@} */
89
90/**@name Event handler properties
91 *
92 * @{
93 */
94
95#define EVENTHDLR_NAME "bounddisjunction"
96#define EVENTHDLR_DESC "event handler for bound disjunction constraints"
97
98/**@} */
99
100/**@name Conflict handler properties
101 *
102 * @{
103 */
104
105#define CONFLICTHDLR_NAME "bounddisjunction"
106#define CONFLICTHDLR_DESC "conflict handler creating bound disjunction constraints"
107#define CONFLICTHDLR_PRIORITY -3000000
108
109/**@} */
110
111/**@name Default parameter values
112 *
113 * @{
114 */
115
116#define DEFAULT_CONTINUOUSFRAC 0.4 /**< maximal percantage of continuous variables within a conflict */
117
118/**@} */
119
120/**@name Age increase defines
121 *
122 * @{
123 */
124
125/* @todo make this a parameter setting */
126#if 1 /* @todo test which AGEINCREASE formula is better! */
127#define AGEINCREASE(n) (1.0 + 0.2*n)
128#else
129#define AGEINCREASE(n) (0.1*n)
130#endif
131
132/**@} */
133
134
135/**@name Comparison for two values
136 *
137 * @{
138 */
139
140#ifdef SCIP_DISABLED_CODE /* These only work if one also passes integral values in case of integral variables. This is not always the case and not even asserted. */
141/** use defines for numeric compare methods to be slightly faster for integral values */
142#define isFeasLT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > 0.5 : SCIPisFeasLT(scip, val1, val2))
143#define isFeasLE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > -0.5 : SCIPisFeasLE(scip, val1, val2))
144#define isFeasGT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > 0.5 : SCIPisFeasGT(scip, val1, val2))
145#define isFeasGE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > -0.5 : SCIPisFeasGE(scip, val1, val2))
146#else
147#define isFeasLT(scip, var, val1, val2) SCIPisFeasLT(scip, val1, val2)
148#define isFeasLE(scip, var, val1, val2) SCIPisFeasLE(scip, val1, val2)
149#define isFeasGT(scip, var, val1, val2) SCIPisFeasGT(scip, val1, val2)
150#define isFeasGE(scip, var, val1, val2) SCIPisFeasGE(scip, val1, val2)
151#endif
152/**@} */
153
154
155/** constraint handler data */
156struct SCIP_ConshdlrData
157{
158 SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
159};
160
161/** bound disjunction constraint data */
162struct SCIP_ConsData
163{
164 SCIP_VAR** vars; /**< variables of the literals in the constraint */
165 SCIP_BOUNDTYPE* boundtypes; /**< types of bounds of the literals (lower or upper bounds) */
166 SCIP_Real* bounds; /**< bounds of the literals */
167 int varssize; /**< size of vars, boundtypes, and bounds arrays */
168 int nvars; /**< number of variables in the constraint */
169 int watchedvar1; /**< position of the first watched variable */
170 int watchedvar2; /**< position of the second watched variable */
171 int filterpos1; /**< event filter position of first watched variable */
172 int filterpos2; /**< event filter position of second watched variable */
173};
174
175/**@name Local methods
176 *
177 * @{
178 */
179
180/** adds rounding locks for the given variable in the given bound disjunction constraint */
181static
183 SCIP* scip, /**< SCIP data structure */
184 SCIP_CONS* cons, /**< bound disjunction constraint */
185 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
186 int pos /**< position of the variable in the constraint */
187 )
188{
189 assert(consdata != NULL);
190 assert(0 <= pos && pos < consdata->nvars);
191
192 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
193 {
194 SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) );
195 }
196 else
197 {
198 SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) );
199 }
200
201 return SCIP_OKAY;
202}
203
204/** removes rounding locks for the given variable in the given bound disjunction constraint */
205static
207 SCIP* scip, /**< SCIP data structure */
208 SCIP_CONS* cons, /**< bound disjunction constraint */
209 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
210 int pos /**< position of the variable in the constraint */
211 )
212{
213 assert(consdata != NULL);
214 assert(0 <= pos && pos < consdata->nvars);
215
216 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
217 {
218 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) );
219 }
220 else
221 {
222 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) );
223 }
224
225 return SCIP_OKAY;
226}
227
228/** catches the events on a single variable of the bound disjunction constraint */
229static
231 SCIP* scip, /**< SCIP data structure */
232 SCIP_CONS* cons, /**< bound disjunction constraint */
233 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
234 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
235 int pos, /**< position of the variable in the constraint */
236 int* filterpos /**< pointer to store position of event filter entry, or NULL */
237 )
238{
239 assert(consdata != NULL);
240 assert(0 <= pos && pos < consdata->nvars);
241
242 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
243 {
245 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
246 }
247 else
248 {
250 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
251 }
252
253 return SCIP_OKAY;
254}
255
256/** drops the events on a single variable of the bound disjunction constraint */
257static
259 SCIP* scip, /**< SCIP data structure */
260 SCIP_CONS* cons, /**< bound disjunction constraint */
261 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
262 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
263 int pos, /**< position of the variable in the constraint */
264 int filterpos /**< position of event filter entry returned by SCIPcatchVarEvent(), or -1 */
265 )
266{
267 assert(consdata != NULL);
268 assert(0 <= pos && pos < consdata->nvars);
269
270 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
271 {
273 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
274 }
275 else
276 {
278 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
279 }
280
281 return SCIP_OKAY;
282}
283
284/** creates constraint handler data for bound disjunction constraint handler */
285static
287 SCIP* scip, /**< SCIP data structure */
288 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
289 SCIP_EVENTHDLR* eventhdlr /**< event handler */
290 )
291{
292 assert(scip != NULL);
293 assert(conshdlrdata != NULL);
294 assert(eventhdlr != NULL);
295
296 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
297
298 /* set event handler for catching events on watched variables */
299 (*conshdlrdata)->eventhdlr = eventhdlr;
300
301 return SCIP_OKAY;
302}
303
304/** frees constraint handler data for bound disjunction constraint handler */
305static
307 SCIP* scip, /**< SCIP data structure */
308 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
309 )
310{
311 assert(conshdlrdata != NULL);
312 assert(*conshdlrdata != NULL);
313
314 SCIPfreeBlockMemory(scip, conshdlrdata);
315}
316
317/** creates a bound disjunction constraint data object */
318static
320 SCIP* scip, /**< SCIP data structure */
321 SCIP_CONSDATA** consdata, /**< pointer to store the bound disjunction constraint data */
322 int nvars, /**< number of variables in the constraint */
323 SCIP_VAR** vars, /**< variables of the literals in the constraint */
324 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
325 SCIP_Real* bounds /**< bounds of the literals */
326 )
327{
328 assert(consdata != NULL);
329 assert(nvars == 0 || vars != NULL);
330 assert(nvars == 0 || boundtypes != NULL);
331 assert(nvars == 0 || bounds != NULL);
332
333 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
334
335 if( nvars > 0 )
336 {
338 {
339 int k;
340 int v;
341#ifndef NDEBUG
342 int nviolations = 0;
343#endif
344 SCIP_Bool redundant;
345 SCIP_VAR** varsbuffer;
346 SCIP_BOUNDTYPE* boundtypesbuffer;
347 SCIP_Real* boundsbuffer;
348
349 SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
350 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesbuffer, nvars) );
351 SCIP_CALL( SCIPallocBufferArray(scip, &boundsbuffer, nvars) );
352
353 k = 0;
354 redundant = FALSE;
355 /* loop over variables, compare fixed ones against its bound disjunction */
356 for( v = 0; v < nvars && !redundant; ++v )
357 {
358 SCIP_VAR* var = vars[v];
359 SCIP_BOUNDTYPE boundtype = boundtypes[v];
360 SCIP_Real bound = bounds[v];
361
362 /* is the variable fixed? */
364 {
365 if( (boundtype == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPvarGetLbLocal(var), bound))
366 || (boundtype == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPvarGetUbLocal(var), bound)) )
367 {
368 /* save this feasible assignment at the first position */
369 varsbuffer[0] = var;
370 boundtypesbuffer[0] = boundtype;
371 boundsbuffer[0] = bound;
372 k = 1;
373 redundant = TRUE;
374 }
375#ifndef NDEBUG
376 else
377 ++nviolations;
378#endif
379 }
380 else
381 {
382 /* append unfixed variable to buffer */
383 varsbuffer[k] = var;
384 boundtypesbuffer[k] = boundtype;
385 boundsbuffer[k] = bound;
386 ++k;
387 }
388 }
389
390 /* duplicate a single, infeasible assignment, wlog the first one */
391 if( k == 0 )
392 {
393 assert(nviolations == nvars);
394 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, 1) );
395 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypes, 1) );
396 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, bounds, 1) );
397 (*consdata)->varssize = 1;
398 (*consdata)->nvars = 1;
399 }
400 else
401 {
402 /* if the bound disjunction is already trivially satisfied, we keep only a single feasible assignment */
403 assert(!redundant || k == 1);
404
405 /* we only copy the buffered variables required to represent the constraint */
406 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
407 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypesbuffer, k) );
408 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, boundsbuffer, k) );
409 (*consdata)->varssize = k;
410 (*consdata)->nvars = k;
411 }
412
413 /* free buffer storage */
414 SCIPfreeBufferArray(scip, &boundsbuffer);
415 SCIPfreeBufferArray(scip, &boundtypesbuffer);
416 SCIPfreeBufferArray(scip, &varsbuffer);
417 }
418 else
419 {
420 /* without problem compression, the entire vars array is copied */
421 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
422 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypes, nvars) );
423 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, bounds, nvars) );
424 (*consdata)->varssize = nvars;
425 (*consdata)->nvars = nvars;
426 }
427 }
428 else
429 {
430 (*consdata)->vars = NULL;
431 (*consdata)->boundtypes = NULL;
432 (*consdata)->bounds = NULL;
433 (*consdata)->varssize = 0;
434 (*consdata)->nvars = 0;
435 }
436 (*consdata)->watchedvar1 = -1;
437 (*consdata)->watchedvar2 = -1;
438 (*consdata)->filterpos1 = -1;
439 (*consdata)->filterpos2 = -1;
440
441 /* get transformed variables, if we are in the transformed problem */
443 {
444 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
445 }
446
447 return SCIP_OKAY;
448}
449
450/** creates a bound disjunction constraint data object with possibly redundant literals */
451static
453 SCIP* scip, /**< SCIP data structure */
454 SCIP_CONSDATA** consdata, /**< pointer to store the bound disjunction constraint data */
455 int nvars, /**< number of variables in the constraint */
456 SCIP_VAR** vars, /**< variables of the literals in the constraint */
457 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
458 SCIP_Real* bounds /**< bounds of the literals */
459 )
460{
461 assert(consdata != NULL);
462 assert(nvars == 0 || vars != NULL);
463 assert(nvars == 0 || boundtypes != NULL);
464 assert(nvars == 0 || bounds != NULL);
465
466 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
467
468 if( nvars > 0 )
469 {
470 SCIP_BOUNDTYPE* boundtypesbuffer;
471 SCIP_Real* boundsbuffer;
472 SCIP_VAR** varsbuffer;
473 SCIP_VAR* var;
474 int nvarsbuffer = 0;
475 int nviolated = 0;
476 int v = 0;
477
478 SCIP_CALL( SCIPduplicateBufferArray(scip, &varsbuffer, vars, nvars) );
479 SCIP_CALL( SCIPduplicateBufferArray(scip, &boundtypesbuffer, boundtypes, nvars) );
480 SCIP_CALL( SCIPduplicateBufferArray(scip, &boundsbuffer, bounds, nvars) );
481
482 /* sort variables according to index; this allows us to check for redundancy easily below because duplicate
483 * variables must now appear consecutively */
484 SCIPsortPtrRealInt((void**)varsbuffer, boundsbuffer, (int*) boundtypesbuffer, SCIPvarComp, nvars);
485
486 /* filter out redundant literals */
487 while( v < nvars )
488 {
489 int lowerindex;
490 int upperindex;
491
492 var = varsbuffer[v];
493
494 /* compress fixed variables */
496 {
497 /* if the literal is feasible for the fixed variable, then the whole constraint is feasible, so we reduce
498 * it to only this literal
499 */
500 if( ( boundtypesbuffer[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPvarGetLbLocal(var), boundsbuffer[v]) )
501 || ( boundtypesbuffer[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPvarGetUbLocal(var), boundsbuffer[v]) ) )
502 {
503 /* save this feasible assignment at the first position */
504 varsbuffer[0] = var;
505 boundtypesbuffer[0] = boundtypesbuffer[v];
506 boundsbuffer[0] = boundsbuffer[v];
507 nvarsbuffer = 1;
508 break;
509 }
510 else
511 {
512 /* otherwise the literal is violated - we skip the literal */
513 ++nviolated;
514 ++v;
515 continue;
516 }
517 }
518
519 /* initialize bound indices */
520 if( boundtypesbuffer[v] == SCIP_BOUNDTYPE_LOWER )
521 {
522 lowerindex = v;
523 upperindex = -1;
524 }
525 else
526 {
527 assert(boundtypesbuffer[v] == SCIP_BOUNDTYPE_UPPER);
528
529 lowerindex = -1;
530 upperindex = v;
531 }
532
533 ++v;
534
535 /* check subsequent variables with the same variable for redundancy */
536 while( v < nvars && varsbuffer[v] == var )
537 {
538 if( boundtypesbuffer[v] == SCIP_BOUNDTYPE_LOWER )
539 {
540 /* keep the weaker lower bound */
541 if( lowerindex == -1 || boundsbuffer[lowerindex] > boundsbuffer[v] )
542 lowerindex = v;
543 }
544 else
545 {
546 assert(boundtypesbuffer[v] == SCIP_BOUNDTYPE_UPPER);
547
548 /* keep the weaker upper bound */
549 if( upperindex == -1 || boundsbuffer[upperindex] < boundsbuffer[v] )
550 upperindex = v;
551 }
552
553 ++v;
554 }
555
556 /* keep bound sequence */
557 if( upperindex != -1 && lowerindex > upperindex )
558 SCIPswapInts(&lowerindex, &upperindex);
559
560 /* keep first bound */
561 if( lowerindex != -1 )
562 {
563 assert(nvarsbuffer != upperindex);
564
565 varsbuffer[nvarsbuffer] = varsbuffer[lowerindex];
566 boundtypesbuffer[nvarsbuffer] = boundtypesbuffer[lowerindex];
567 boundsbuffer[nvarsbuffer] = boundsbuffer[lowerindex];
568 ++nvarsbuffer;
569 }
570
571 /* keep second bound */
572 if( upperindex != -1 )
573 {
574 varsbuffer[nvarsbuffer] = varsbuffer[upperindex];
575 boundtypesbuffer[nvarsbuffer] = boundtypesbuffer[upperindex];
576 boundsbuffer[nvarsbuffer] = boundsbuffer[upperindex];
577 ++nvarsbuffer;
578 }
579 }
580 assert(nvarsbuffer > 0 || SCIPisConsCompressionEnabled(scip)); /* no variables can only happen if compression is enabled */
581
582#ifndef NDEBUG
583 /* if there are no variables left, this is because all literals are infeasible */
584 if( nvarsbuffer == 0 )
585 {
586 for( v = 0; v < nvars; v++ )
587 {
588 var = vars[v];
589 assert( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) );
590 assert( (boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, SCIPvarGetLbLocal(var), bounds[v]))
591 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, SCIPvarGetUbLocal(var), bounds[v])) );
592 }
593 }
594 else
595 {
596 /* check that the literals are not redundant */
597 for( v = 0; v < nvarsbuffer; v++ )
598 {
599 int v2;
600 assert(varsbuffer[v] != NULL);
601 for( v2 = v+1; v2 < nvarsbuffer; v2++ )
602 assert(varsbuffer[v] != varsbuffer[v2] || boundtypesbuffer[v] != boundtypesbuffer[v2]);
603 }
604 }
605#endif
606
607 /* if all literals are infeasible, we keep the first */
608 if( SCIPisConsCompressionEnabled(scip) && nviolated > 0 && nvarsbuffer == 0 )
609 nvarsbuffer = 1;
610
611 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, nvarsbuffer) );
612 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypesbuffer, nvarsbuffer) );
613 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, boundsbuffer, nvarsbuffer) );
614 (*consdata)->varssize = nvarsbuffer;
615 (*consdata)->nvars = nvarsbuffer;
616
617 /* free buffer storage */
618 SCIPfreeBufferArray(scip, &boundsbuffer);
619 SCIPfreeBufferArray(scip, &boundtypesbuffer);
620 SCIPfreeBufferArray(scip, &varsbuffer);
621 }
622 else
623 {
624 (*consdata)->vars = NULL;
625 (*consdata)->boundtypes = NULL;
626 (*consdata)->bounds = NULL;
627 (*consdata)->varssize = 0;
628 (*consdata)->nvars = 0;
629 }
630 (*consdata)->watchedvar1 = -1;
631 (*consdata)->watchedvar2 = -1;
632 (*consdata)->filterpos1 = -1;
633 (*consdata)->filterpos2 = -1;
634
635 /* get transformed variables, if we are in the transformed problem */
637 {
638 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
639 }
640
641 return SCIP_OKAY;
642}
643
644/** frees a bound disjunction constraint data */
645static
647 SCIP* scip, /**< SCIP data structure */
648 SCIP_CONSDATA** consdata /**< pointer to the bound disjunction constraint */
649 )
650{
651 assert(consdata != NULL);
652 assert(*consdata != NULL);
653
654 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
655 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->boundtypes, (*consdata)->varssize);
656 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->bounds, (*consdata)->varssize);
657 SCIPfreeBlockMemory(scip, consdata);
658}
659
660/** prints bound disjunction constraint to file stream */
661static
663 SCIP* scip, /**< SCIP data structure */
664 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
665 FILE* file, /**< output file (or NULL for standard output) */
666 SCIP_Bool endline /**< should an endline be set? */
667 )
668{
669 int v;
670
671 assert(consdata != NULL);
672
673 /* print coefficients */
674 SCIPinfoMessage(scip, file, "bounddisjunction(");
675 for( v = 0; v < consdata->nvars; ++v )
676 {
677 assert(consdata->vars[v] != NULL);
678 if( v > 0 )
679 SCIPinfoMessage(scip, file, ", ");
680 SCIPinfoMessage(scip, file, "<%s> %s %.15g", SCIPvarGetName(consdata->vars[v]),
681 consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", consdata->bounds[v]);
682 }
683 SCIPinfoMessage(scip, file, ")");
684
685 if( endline )
686 SCIPinfoMessage(scip, file, "\n");
687}
688
689/** stores the given variable numbers as watched variables, and updates the event processing */
690static
692 SCIP* scip, /**< SCIP data structure */
693 SCIP_CONS* cons, /**< bound disjunction constraint */
694 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
695 int watchedvar1, /**< new first watched variable */
696 int watchedvar2 /**< new second watched variable */
697 )
698{
699 SCIP_CONSDATA* consdata;
700
701 consdata = SCIPconsGetData(cons);
702 assert(consdata != NULL);
703 assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
704 assert(watchedvar1 != -1 || watchedvar2 == -1);
705 assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
706 assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
707
708 /* don't watch variables for non active constraints */
709 if( !SCIPconsIsActive(cons) )
710 return SCIP_OKAY;
711
712 /* if one watched variable is equal to the old other watched variable, just switch positions */
713 if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
714 {
715 int tmp;
716
717 tmp = consdata->watchedvar1;
718 consdata->watchedvar1 = consdata->watchedvar2;
719 consdata->watchedvar2 = tmp;
720 tmp = consdata->filterpos1;
721 consdata->filterpos1 = consdata->filterpos2;
722 consdata->filterpos2 = tmp;
723 }
724 assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
725 assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
726
727 /* drop events on old watched variables */
728 if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
729 {
730 assert(consdata->filterpos1 != -1);
731 SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
732 consdata->watchedvar1 = -1;
733 }
734 if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
735 {
736 assert(consdata->filterpos2 != -1);
737 SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
738 consdata->watchedvar2 = -1;
739 }
740
741 /* catch events on new watched variables */
742 if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
743 {
744 SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) );
745 }
746 if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
747 {
748 SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) );
749 }
750
751 /* set the new watched variables */
752 consdata->watchedvar1 = watchedvar1;
753 consdata->watchedvar2 = watchedvar2;
754
755 return SCIP_OKAY;
756}
757
758/** check whether two intervals overlap */
759static
761 SCIP* scip,
762 SCIP_VAR* var,
763 SCIP_BOUNDTYPE boundtype1,
764 SCIP_Real bound1,
765 SCIP_BOUNDTYPE boundtype2,
766 SCIP_Real bound2
767 )
768{
769 SCIP_Bool overlapping = FALSE;
770
771 if( boundtype1 == SCIP_BOUNDTYPE_LOWER )
772 {
773 assert(boundtype2 == SCIP_BOUNDTYPE_UPPER);
774
775 if( SCIPisLE(scip, bound1 - bound2, (SCIP_Real)SCIPvarIsIntegral(var)) )
776 overlapping = TRUE;
777 }
778 else
779 {
780 assert(boundtype2 == SCIP_BOUNDTYPE_LOWER);
781
782 if( SCIPisLE(scip, bound2 - bound1, (SCIP_Real)SCIPvarIsIntegral(var)) )
783 overlapping = TRUE;
784 }
785
786 return overlapping;
787}
788
789/** deletes coefficient at given position from bound disjunction constraint data */
790static
792 SCIP* scip, /**< SCIP data structure */
793 SCIP_CONS* cons, /**< bound disjunction constraint */
794 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
795 int pos /**< position of coefficient to delete */
796 )
797{
798 SCIP_CONSDATA* consdata;
799
800 assert(eventhdlr != NULL);
801
802 consdata = SCIPconsGetData(cons);
803 assert(consdata != NULL);
804 assert(0 <= pos && pos < consdata->nvars);
805 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
806
807 /* remove the rounding locks of variable */
808 SCIP_CALL( unlockRounding(scip, cons, consdata, pos) );
809
810 if( SCIPconsIsTransformed(cons) )
811 {
812 /* if the position is watched, stop watching the position */
813 if( consdata->watchedvar1 == pos )
814 {
815 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar2, -1) );
816 }
817 if( consdata->watchedvar2 == pos )
818 {
819 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, -1) );
820 }
821 }
822 assert(pos != consdata->watchedvar1);
823 assert(pos != consdata->watchedvar2);
824
825 /* move the last variable to the free slot */
826 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
827 consdata->boundtypes[pos] = consdata->boundtypes[consdata->nvars-1];
828 consdata->bounds[pos] = consdata->bounds[consdata->nvars-1];
829 consdata->nvars--;
830
831 /* if the last variable (that moved) was watched, update the watched position */
832 if( consdata->watchedvar1 == consdata->nvars )
833 consdata->watchedvar1 = pos;
834 if( consdata->watchedvar2 == consdata->nvars )
835 consdata->watchedvar2 = pos;
836
838
839 return SCIP_OKAY;
840}
841
842/** adds literal to bound disjunction constraint data */
843static
845 SCIP* scip, /**< SCIP data structure */
846 SCIP_CONS* cons, /**< bound disjunction constraint */
847 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
848 SCIP_VAR* var, /**< variable in literal */
849 SCIP_BOUNDTYPE boundtype, /**< boundtype of literal */
850 SCIP_Real bound, /**< bound of literal */
851 SCIP_Bool* redundant /**< flag to indicate whether constraint has been bound redundant */
852 )
853{
854 SCIP_CONSDATA* consdata;
855 int samebndidx;
856 int v;
857
858 assert(eventhdlr != NULL);
859
860 consdata = SCIPconsGetData(cons);
861 assert(consdata != NULL);
862 assert(var != NULL);
863 assert(!SCIPisInfinity(scip, REALABS(bound)));
864 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
865
866 /* ensure enough memory in consdata arrays */
867 if( consdata->varssize == consdata->nvars )
868 {
869 int newsize;
870
871 newsize = SCIPcalcMemGrowSize(scip, consdata->nvars + 1);
872 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
873 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->boundtypes, consdata->varssize, newsize) );
874 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bounds, consdata->varssize, newsize) );
875 consdata->varssize = newsize;
876 }
877 assert(consdata->varssize > consdata->nvars);
878
879 /* remember the position of the literal in the constraint that has the same bound type on the same variable
880 *
881 * example: (x >= 5) or (x <= 2) and literal (x >= 2) should be added.
882 * if we see (x >= 5) first, we cannot stop immediately because only in combination with the second literal
883 * we see that the constraint is redundant.
884 */
885 samebndidx = -1;
886
887 for( v = 0; v < consdata->nvars; v++ )
888 {
889 /* check if the variable is already part of the constraint */
890 if( consdata->vars[v] == var )
891 {
892 if( consdata->boundtypes[v] == boundtype )
893 samebndidx = v;
894 else if( isOverlapping(scip, var, consdata->boundtypes[v], consdata->bounds[v], boundtype, bound) )
895 {
896 *redundant = TRUE;
897 return SCIP_OKAY;
898 }
899 }
900 }
901
902 /* the combination of variable and boundtype is already part of the constraint; check whether the clause
903 * can be relaxed
904 */
905 if( samebndidx > -1 )
906 {
907 if( (boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLT(scip, bound, consdata->bounds[samebndidx]))
908 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisGT(scip, bound, consdata->bounds[samebndidx])) )
909 {
910 SCIPdebugMsg(scip, "relax clause of <%s>: (<%s> %s %.15g) -> (<%s> %s %.15g)\n", SCIPconsGetName(cons),
911 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", consdata->bounds[samebndidx],
912 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bound);
913 consdata->bounds[samebndidx] = bound;
914 }
915 }
916 else
917 {
918 /* add the variable to the end of the array */
919 consdata->vars[consdata->nvars] = var;
920 consdata->boundtypes[consdata->nvars] = boundtype;
921 consdata->bounds[consdata->nvars] = bound;
922 consdata->nvars++;
923
924 if( SCIPconsIsTransformed(cons) )
925 {
926 /* add rounding lock of variable */
927 SCIP_CALL( lockRounding(scip, cons, consdata, consdata->nvars-1) );
928
929 /* if less than 2 variables are watched, add the new one to the watched variables */
930 if( consdata->watchedvar1 == -1 )
931 {
932 assert(consdata->watchedvar2 == -1);
933 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->nvars-1, -1) );
934 }
935 else if( consdata->watchedvar2 == -1 )
936 {
937 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, consdata->nvars-1) );
938 }
939 }
940 }
941
943
944 return SCIP_OKAY;
945}
946
947/** deletes all variables with global bounds violating the literal, checks for global bounds satisfying the literal */
948static
950 SCIP* scip, /**< SCIP data structure */
951 SCIP_CONS* cons, /**< bound disjunction constraint */
952 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
953 SCIP_Bool* redundant /**< returns whether a variable fixed to one exists in the constraint */
954 )
955{
956 SCIP_CONSDATA* consdata;
957 int v;
958 SCIP_Real bnd;
959
960 assert(eventhdlr != NULL);
961 assert(redundant != NULL);
962
963 consdata = SCIPconsGetData(cons);
964 assert(consdata != NULL);
965 assert(consdata->nvars == 0 || consdata->vars != NULL);
966
967 *redundant = FALSE;
968 v = 0;
969 while( v < consdata->nvars )
970 {
971 SCIP_VAR* var;
972
973 var = consdata->vars[v];
974
975 if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
976 {
977 bnd = SCIPcomputeVarLbGlobal(scip, var);
978 if( isFeasGE(scip, var, bnd, consdata->bounds[v]) )
979 {
980 *redundant = TRUE;
981 return SCIP_OKAY;
982 }
983 else
984 {
985 bnd = SCIPcomputeVarUbGlobal(scip, var);
986 if( isFeasLT(scip, var, bnd, consdata->bounds[v]) )
987 {
988 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
989 }
990 else
991 ++v;
992 }
993 }
994 else
995 {
996 assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
997 bnd = SCIPcomputeVarUbGlobal(scip, var);
998 if( isFeasLE(scip, var, bnd, consdata->bounds[v]) )
999 {
1000 *redundant = TRUE;
1001 return SCIP_OKAY;
1002 }
1003 else
1004 {
1005 bnd = SCIPcomputeVarLbGlobal(scip, var);
1006 if( isFeasGT(scip, var, bnd, consdata->bounds[v]) )
1007 {
1008 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1009 }
1010 else
1011 ++v;
1012 }
1013 }
1014 }
1015
1016 SCIPdebugMsg(scip, "after global bounds: ");
1017 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
1018
1019 return SCIP_OKAY;
1020}
1021
1022/** returns whether literal at the given position is satisfied in the local bounds */
1023static
1025 SCIP* scip, /**< SCIP data structure */
1026 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
1027 int pos /**< position of the literal */
1028 )
1029{
1030 SCIP_Real bnd;
1031
1032 assert(consdata != NULL);
1033 assert(0 <= pos && pos < consdata->nvars);
1034
1035 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
1036 {
1037 bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]);
1038 return isFeasGE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1039 }
1040 else
1041 {
1042 bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]);
1043 return isFeasLE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1044 }
1045}
1046
1047/** returns whether literal at the given position is violated in the local bounds */
1048static
1050 SCIP* scip, /**< SCIP data structure */
1051 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
1052 int pos /**< position of the literal */
1053 )
1054{
1055 SCIP_Real bnd;
1056
1057 assert(consdata != NULL);
1058 assert(0 <= pos && pos < consdata->nvars);
1059
1060 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
1061 {
1062 bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]);
1063 return isFeasLT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1064 }
1065 else
1066 {
1067 bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]);
1068 return isFeasGT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1069 }
1070}
1071
1072/** replace variables by their representative active (or multi-aggregated) variables */
1073static
1075 SCIP* scip, /**< SCIP data structure */
1076 SCIP_CONS* cons, /**< bound disjunction constraint */
1077 SCIP_EVENTHDLR* eventhdlr, /**< event handler */
1078 SCIP_Bool* redundant /**< flag to indicate whether constraint has been bound redundant */
1079 )
1080{
1081 SCIP_CONSDATA* consdata;
1082 SCIP_VAR* var;
1083 SCIP_BOUNDTYPE boundtype;
1085 int v;
1086
1087 assert(scip != NULL);
1088 assert(cons != NULL);
1089 assert(eventhdlr != NULL);
1090
1091 consdata = SCIPconsGetData(cons);
1092 assert(consdata != NULL);
1093
1094 v = 0;
1095 while( v < consdata->nvars )
1096 {
1097#ifndef NDEBUG
1098 SCIP_VAR* oldvar;
1099#endif
1100 var = consdata->vars[v];
1101 assert(var != NULL);
1102
1103#ifndef NDEBUG
1104 oldvar = var;
1105#endif
1106
1108 {
1109 /* check whether the literal is satisfied and the constraint is thus redundant */
1110 if( isLiteralSatisfied(scip, consdata, v) )
1111 {
1112 *redundant = TRUE;
1113 break;
1114 }
1115 if( isLiteralViolated(scip, consdata, v) )
1116 {
1117 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1118 continue;
1119 }
1120
1121 ++v;
1122
1123 continue;
1124 }
1125
1126 /* get active/fixed/multiaggr equivalent of v'th literal */
1127 bound = consdata->bounds[v];
1128 boundtype = consdata->boundtypes[v];
1129 SCIP_CALL( SCIPvarGetProbvarBound(&var, &bound, &boundtype) );
1130 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || oldvar != var);
1131
1132 SCIPdebugMsg(scip, "in <%s>, replace <%s>[%g,%g] %c= %g by <%s>[%g,%g] %c= %g\n", SCIPconsGetName(cons),
1133 SCIPvarGetName(consdata->vars[v]), SCIPvarGetLbGlobal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]), (consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), consdata->bounds[v],
1134 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), (boundtype == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), bound);
1135
1136 /* if literal is satisfied, then constraint is redundant and we can stop */
1137 if( (boundtype == SCIP_BOUNDTYPE_LOWER && isFeasLE(scip, var, bound, SCIPvarGetLbGlobal(var))) || /*lint !e666*/
1138 (boundtype == SCIP_BOUNDTYPE_UPPER && isFeasGE(scip, var, bound, SCIPvarGetUbGlobal(var))) ) /*lint !e666*/
1139 {
1140 *redundant = TRUE;
1141 break;
1142 }
1143
1144 /* if literal is not fixed, replace it */
1146 {
1147 /* add new literal */
1148 SCIP_CALL( addCoef(scip, cons, eventhdlr, var, boundtype, bound, redundant) );
1149 }
1150
1151 /* remove old literal */
1152 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1153 }
1154
1155 return SCIP_OKAY;
1156}
1157
1158/** try to upgrade the bounddisjunction constraint
1159 *
1160 * if only binary variables are left, we can upgrade a bounddisjunction to a logicor constraint(, if only two variables
1161 * are left, this logicor constraint can be formulated as set-packing constraint as well)
1162 *
1163 * e.g.: bounddisjunction( x1 >= 1, x2 <= 0; x3 >= 1; x4 <= 0 ) => x1 + ~x2 + x3 + ~x4 >= 1
1164 */
1165static
1167 SCIP* scip, /**< SCIP data structure */
1168 SCIP_CONS* cons, /**< bound disjunction constraint that detected the conflict */
1169 int* ndelconss, /**< pointer to store the number of delete constraint */
1170 int* naddconss /**< pointer to store the number of added constraint */
1171 )
1172{
1173 SCIP_CONSDATA* consdata;
1174 SCIP_VAR** newvars;
1175 SCIP_Bool allbinary;
1176 int nvars;
1177 int v;
1178
1179 assert(scip != NULL);
1180 assert(cons != NULL);
1181 assert(ndelconss != NULL);
1182 assert(naddconss != NULL);
1183 assert(naddconss != NULL);
1184 assert(!SCIPconsIsModifiable(cons));
1185
1186 consdata = SCIPconsGetData(cons);
1187 assert(consdata != NULL);
1188
1189 nvars = consdata->nvars;
1190 assert(nvars >= 2);
1191 assert(consdata->vars != NULL);
1192
1193 allbinary = TRUE;
1194
1195 SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars) );
1196
1197 for( v = nvars - 1; v >= 0; --v )
1198 {
1199 if( !SCIPvarIsBinary(consdata->vars[v]) )
1200 {
1201 allbinary = FALSE;
1202 break;
1203 }
1204 else
1205 {
1206 if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1207 {
1208 assert(SCIPisFeasGT(scip, consdata->bounds[v], 0.0));
1209
1210 if( nvars == 2 )
1211 {
1212 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) );
1213 }
1214 else
1215 newvars[v] = consdata->vars[v];
1216 }
1217 else
1218 {
1219 assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
1220 assert(SCIPisFeasLT(scip, consdata->bounds[v], 1.0));
1221
1222 if( nvars > 2 )
1223 {
1224 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) );
1225 }
1226 else
1227 newvars[v] = consdata->vars[v];
1228 }
1229 }
1230 }
1231
1232 if( allbinary )
1233 {
1234 SCIP_CONS* newcons;
1235
1236 if( nvars == 2 )
1237 {
1238 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), nvars, newvars,
1243 }
1244 else
1245 {
1246 SCIP_CALL( SCIPcreateConsLogicor(scip, &newcons, SCIPconsGetName(cons), nvars, newvars,
1251 }
1252
1253 SCIPdebugMsg(scip, "updated constraint <%s> to the following %s constraint\n", SCIPconsGetName(cons), (nvars == 2 ? "setppc" : "logicor"));
1254 SCIPdebugPrintCons(scip, newcons, NULL);
1255 SCIP_CALL( SCIPaddCons(scip, newcons) );
1256 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1257 ++(*naddconss);
1258
1259 SCIP_CALL( SCIPdelCons(scip, cons) );
1260 ++(*ndelconss);
1261 }
1262
1263 SCIPfreeBufferArray(scip, &newvars);
1264
1265 return SCIP_OKAY;
1266}
1267
1268/** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
1269static
1271 SCIP* scip, /**< SCIP data structure */
1272 SCIP_CONS* cons /**< bound disjunction constraint that detected the conflict */
1273 )
1274{
1275 SCIP_CONSDATA* consdata;
1276 int v;
1277
1278 /* conflict analysis can only be applied in solving stage and if it is turned on */
1280 return SCIP_OKAY;
1281
1282 consdata = SCIPconsGetData(cons);
1283 assert(consdata != NULL);
1284
1285 /* initialize conflict analysis, and add all bounds of infeasible constraint to conflict candidate queue */
1287
1288 for( v = 0; v < consdata->nvars; ++v )
1289 {
1290 /* the opposite bound is in conflict with this literal */
1291 SCIP_CALL( SCIPaddConflictBd(scip, consdata->vars[v], SCIPboundtypeOpposite(consdata->boundtypes[v]), NULL) );
1292 }
1293
1294 /* analyze the conflict */
1296
1297 return SCIP_OKAY;
1298}
1299
1300/** disables or deletes the given constraint, depending on the current depth */
1301static
1303 SCIP* scip, /**< SCIP data structure */
1304 SCIP_CONS* cons /**< bound disjunction constraint to be disabled */
1305 )
1306{
1307 assert(SCIPconsGetValidDepth(cons) <= SCIPgetDepth(scip));
1308
1310 {
1311 SCIP_CALL( SCIPdelCons(scip, cons) );
1312 }
1313 else
1314 {
1315 SCIP_CALL( SCIPdisableCons(scip, cons) );
1316 }
1317
1318 return SCIP_OKAY;
1319}
1320
1321/** checks constraint for violation only looking at the watched variables, applies bound changes if possible */
1322static
1324 SCIP* scip, /**< SCIP data structure */
1325 SCIP_CONS* cons, /**< bound disjunction constraint to be processed */
1326 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1327 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1328 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint is infeasible in current bounds */
1329 SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
1330 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
1331 )
1332{
1333 SCIP_CONSDATA* consdata;
1334 SCIP_VAR** vars;
1335 SCIP_BOUNDTYPE* boundtypes;
1336 SCIP_Real* bounds;
1337 SCIP_Longint nbranchings1;
1338 SCIP_Longint nbranchings2;
1339 int nvars;
1340 int watchedvar1;
1341 int watchedvar2;
1342
1343 assert(cons != NULL);
1344 assert(SCIPconsGetHdlr(cons) != NULL);
1345 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1346 assert(cutoff != NULL);
1347 assert(reduceddom != NULL);
1348 assert(mustcheck != NULL);
1349
1350 consdata = SCIPconsGetData(cons);
1351 assert(consdata != NULL);
1352 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
1353
1354 /* init bools */
1355 *cutoff = FALSE;
1356 *infeasible = FALSE;
1357 *reduceddom = FALSE;
1358 *mustcheck = FALSE;
1359
1360 SCIPdebugMsg(scip, "processing watched variables of constraint <%s>\n", SCIPconsGetName(cons));
1361
1362 nvars = consdata->nvars;
1363 vars = consdata->vars;
1364 boundtypes = consdata->boundtypes;
1365 bounds = consdata->bounds;
1366 assert(nvars == 0 || vars != NULL);
1367 assert(nvars == 0 || boundtypes != NULL);
1368 assert(nvars == 0 || bounds != NULL);
1369
1370 /* check watched variables if they are satisfying the literal */
1371 if( consdata->watchedvar1 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar1) )
1372 {
1373 /* the literal is satisfied, making the constraint redundant */
1374 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar1 satisfied)\n", SCIPconsGetName(cons));
1375 SCIP_CALL( disableCons(scip, cons) );
1376 return SCIP_OKAY;
1377 }
1378 if( consdata->watchedvar2 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar2) )
1379 {
1380 /* the literal is satisfied, making the constraint redundant */
1381 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar2 satisfied)\n", SCIPconsGetName(cons));
1382 SCIP_CALL( disableCons(scip, cons) );
1383 return SCIP_OKAY;
1384 }
1385
1386 /* check if watched variables are still undecided */
1387 watchedvar1 = -1;
1388 watchedvar2 = -1;
1389 nbranchings1 = SCIP_LONGINT_MAX;
1390 nbranchings2 = SCIP_LONGINT_MAX;
1391 if( consdata->watchedvar1 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar1) )
1392 {
1393 watchedvar1 = consdata->watchedvar1;
1394 nbranchings1 = -1; /* prefer keeping the watched variable */
1395 }
1396 if( consdata->watchedvar2 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar2) )
1397 {
1398 if( watchedvar1 == -1 )
1399 {
1400 watchedvar1 = consdata->watchedvar2;
1401 nbranchings1 = -1; /* prefer keeping the watched variable */
1402 }
1403 else
1404 {
1405 watchedvar2 = consdata->watchedvar2;
1406 nbranchings2 = -1; /* prefer keeping the watched variable */
1407 }
1408 }
1409 assert(watchedvar1 >= 0 || watchedvar2 == -1);
1410 assert(nbranchings1 <= nbranchings2);
1411 assert(watchedvar1 != -1 || nbranchings1 == SCIP_LONGINT_MAX);
1412 assert(watchedvar2 != -1 || nbranchings2 == SCIP_LONGINT_MAX);
1413
1414 /* search for new watched variables */
1415 if( watchedvar2 == -1 )
1416 {
1417 int v;
1418
1419 for( v = 0; v < nvars; ++v )
1420 {
1421 SCIP_Longint nbranchings;
1422
1423 /* don't process the watched variables again */
1424 if( v == consdata->watchedvar1 || v == consdata->watchedvar2 )
1425 continue;
1426
1427 /* check, if the literal is violated */
1428 if( isLiteralViolated(scip, consdata, v) )
1429 continue;
1430
1431 /* check, if the literal is satisfied */
1432 if( isLiteralSatisfied(scip, consdata, v) )
1433 {
1434 assert(v != consdata->watchedvar1);
1435 assert(v != consdata->watchedvar2);
1436
1437 /* the literal is satisfied, making the constraint redundant;
1438 * make sure, the feasible variable is watched and disable the constraint
1439 */
1440 SCIPdebugMsg(scip, " -> disabling constraint <%s> (variable <%s> fixed to 1.0)\n",
1441 SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
1442 if( consdata->watchedvar1 != -1 )
1443 {
1444 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, v) );
1445 }
1446 else
1447 {
1448 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, v, consdata->watchedvar2) );
1449 }
1450 SCIP_CALL( disableCons(scip, cons) );
1451 return SCIP_OKAY;
1452 }
1453
1454 /* the literal is still undecided and can be used as watched variable */
1455 nbranchings = SCIPvarGetNBranchingsCurrentRun(vars[v],
1457 if( nbranchings < nbranchings2 )
1458 {
1459 if( nbranchings < nbranchings1 )
1460 {
1461 watchedvar2 = watchedvar1;
1462 nbranchings2 = nbranchings1;
1463 watchedvar1 = v;
1464 nbranchings1 = nbranchings;
1465 }
1466 else
1467 {
1468 watchedvar2 = v;
1469 nbranchings2 = nbranchings;
1470 }
1471 }
1472 }
1473 }
1474 assert(nbranchings1 <= nbranchings2);
1475 assert(watchedvar1 >= 0 || watchedvar2 == -1);
1476
1477 if( watchedvar1 == -1 )
1478 {
1479 /* there is no undecided literal left -> the constraint is infeasible
1480 * - a modifiable constraint is infeasible
1481 * - an unmodifiable constraint is infeasible and the node can be cut off
1482 */
1483 assert(watchedvar2 == -1);
1484
1485 SCIPdebugMsg(scip, " -> constraint <%s> is infeasible\n", SCIPconsGetName(cons));
1486 *infeasible = TRUE;
1487
1489 if( !SCIPconsIsModifiable(cons) )
1490 {
1491 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1492 SCIP_CALL( analyzeConflict(scip, cons) );
1493
1494 /* mark the node to be cut off */
1495 *cutoff = TRUE;
1496 }
1497 }
1498 else if( watchedvar2 == -1 )
1499 {
1500 /* there is only one undecided literal:
1501 * - a modifiable constraint must be checked manually
1502 * - we cannot change bounds of multi-aggregated variables and have to check manually
1503 * - an unmodifiable constraint is feasible and can be disabled after the remaining literal is satisfied
1504 */
1505 assert(0 <= watchedvar1 && watchedvar1 < nvars);
1506 assert(!isLiteralViolated(scip, consdata, watchedvar1));
1507 assert(!isLiteralSatisfied(scip, consdata, watchedvar1));
1508 if( SCIPconsIsModifiable(cons)
1510 *mustcheck = TRUE;
1511 else
1512 {
1513 SCIP_Bool infbdchg;
1514
1515#ifndef NDEBUG
1516 int v;
1517
1518 /* check whether all other literals are violated */
1519 for (v = 0; v < nvars; ++v)
1520 {
1521 if ( v != watchedvar1 )
1522 {
1523 assert( isLiteralViolated(scip, consdata, v) );
1524 }
1525 }
1526#endif
1527
1528 /* satisfy remaining literal and disable constraint; make sure, the fixed-to-one variable is watched */
1529 SCIPdebugMsg(scip, " -> single-literal constraint <%s> (change bound <%s> %s %g) at depth %d\n",
1530 SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]),
1531 boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bounds[watchedvar1], SCIPgetDepth(scip));
1532
1533 if( boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER )
1534 {
1535 SCIP_CALL( SCIPinferVarLbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE,
1536 &infbdchg, NULL) );
1537 }
1538 else
1539 {
1540 SCIP_CALL( SCIPinferVarUbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE,
1541 &infbdchg, NULL) );
1542 }
1543 assert(!infbdchg);
1545 if( watchedvar1 != consdata->watchedvar1 ) /* keep one of the watched variables */
1546 {
1547 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, consdata->watchedvar1) );
1548 }
1549 SCIP_CALL( disableCons(scip, cons) );
1550 *reduceddom = TRUE;
1551 }
1552 }
1553 else
1554 {
1555 SCIPdebugMsg(scip, " -> new watched variables <%s> and <%s> of constraint <%s> are still undecided\n",
1556 SCIPvarGetName(vars[watchedvar1]), SCIPvarGetName(vars[watchedvar2]), SCIPconsGetName(cons));
1557
1558 /* switch to the new watched variables */
1559 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, watchedvar2) );
1560
1561 /* there are at least two undecided variables -> the constraint must be checked manually */
1562 *mustcheck = TRUE;
1563
1564 /* disable propagation of constraint until the corresponding bound of a watched variable changed */
1566
1567 /* increase aging counter */
1568 SCIP_CALL( SCIPaddConsAge(scip, cons, AGEINCREASE(consdata->nvars)) );
1569 }
1570
1571 return SCIP_OKAY;
1572}
1573
1574/** checks constraint for violation, returns TRUE iff constraint is violated */
1575static
1577 SCIP* scip, /**< SCIP data structure */
1578 SCIP_CONS* cons, /**< bound disjunction constraint to be checked */
1579 SCIP_SOL* sol /**< primal CIP solution */
1580 )
1581{
1582 SCIP_CONSDATA* consdata;
1583 SCIP_VAR** vars;
1584 SCIP_BOUNDTYPE* boundtypes;
1585 SCIP_Real* bounds;
1586 SCIP_Real solval;
1587 SCIP_Real viol;
1588 SCIP_Real absviol;
1589 int violpos;
1590 int nvars;
1591 int v;
1592
1593 consdata = SCIPconsGetData(cons);
1594 assert(consdata != NULL);
1595
1596 nvars = consdata->nvars;
1597 vars = consdata->vars;
1598 boundtypes = consdata->boundtypes;
1599 bounds = consdata->bounds;
1600 assert(nvars == 0 || vars != NULL);
1601 assert(nvars == 0 || boundtypes != NULL);
1602 assert(nvars == 0 || bounds != NULL);
1603
1604 /* check the given solution */
1605 absviol = SCIP_REAL_MAX;
1606 violpos = -1;
1607 for( v = 0; v < nvars; ++v )
1608 {
1609 solval = SCIPgetSolVal(scip, sol, vars[v]);
1610
1611 /* update absolute violation if needed */
1612 viol = (boundtypes[v] == SCIP_BOUNDTYPE_LOWER) ? bounds[v] - solval : solval - bounds[v];
1613 if( viol < absviol )
1614 {
1615 absviol = viol;
1616 violpos = v;
1617 }
1618
1619 if( (boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, vars[v], solval, bounds[v]))
1620 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, vars[v], solval, bounds[v])) )
1621 {
1622 return FALSE;
1623 }
1624 }
1625 /* update constraint violation in solution */
1626 if( sol != NULL )
1627 {
1628 SCIP_Real relviol;
1629
1630 assert(0 == nvars || -1 != violpos);
1631
1632 if( 0 == nvars )
1633 relviol = SCIP_REAL_MAX;
1634 else
1635 relviol = SCIPrelDiff(SCIPgetSolVal(scip, sol, vars[violpos]), bounds[violpos]);
1636
1637 SCIPupdateSolConsViolation(scip, sol, absviol, relviol);
1638 }
1639 return TRUE;
1640}
1641
1642/* registers variables of a constraint as branching candidates
1643 * indicates whether an n-ary branch is necessary to enforce this constraint,
1644 * because all active literals are w.r.t. continuous variables which bound (in the literal) is at the variable's bound
1645 */
1646static
1648 SCIP* scip, /**< SCIP data structure */
1649 SCIP_CONS* cons, /**< bound disjunction constraint which variables should be registered for branching */
1650 SCIP_SOL* sol, /**< solution (NULL for LP solution) */
1651 SCIP_Bool* cutoff, /**< pointer to store whether the constraint cannot be made feasible by branching */
1652 SCIP_Bool* neednarybranch /**< pointer to store TRUE, if n-ary branching is necessary to enforce this constraint */
1653 )
1654{
1655 SCIP_CONSDATA* consdata;
1656 SCIP_VAR** vars;
1657 SCIP_BOUNDTYPE* boundtypes;
1658 SCIP_Real* bounds;
1659 SCIP_Real violation;
1660 SCIP_Real varlb;
1661 SCIP_Real varub;
1662 int nvars;
1663 int v;
1664
1665 assert(cons != NULL);
1666 assert(SCIPconsGetHdlr(cons) != NULL);
1667 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1668 assert(cutoff != NULL);
1669 assert(neednarybranch != NULL);
1670
1671 consdata = SCIPconsGetData(cons);
1672 assert(consdata != NULL);
1673 nvars = consdata->nvars;
1674 vars = consdata->vars;
1675 boundtypes = consdata->boundtypes;
1676 bounds = consdata->bounds;
1677 assert(nvars == 0 || vars != NULL);
1678 assert(nvars == 0 || boundtypes != NULL);
1679 assert(nvars == 0 || bounds != NULL);
1680
1681 *cutoff = TRUE;
1682 *neednarybranch = TRUE;
1683
1684 for( v = 0; v < nvars; ++v )
1685 {
1686 SCIP_VAR* var;
1687
1688 var = vars[v];
1689 assert(var != NULL);
1690
1691 /* constraint should be violated, so all bounds in the constraint have to be violated */
1692 assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGE(scip, SCIPgetSolVal(scip, sol, var), bounds[v])) &&
1693 !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLE(scip, SCIPgetSolVal(scip, sol, var), bounds[v])) );
1694
1695 varlb = SCIPcomputeVarLbLocal(scip, var);
1696 varub = SCIPcomputeVarUbLocal(scip, var);
1697
1698 /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied,
1699 * thus there is no use for branching
1700 */
1701 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) )
1702 continue;
1703
1704 /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied,
1705 * thus there is no use for branching
1706 */
1707 if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) )
1708 continue;
1709
1710 /* if literal is always satisfied, then no need to branch on it may happen if propagation is disabled for some
1711 * reason and due to numerics current solution does not satisfy literal, but variable bounds do
1712 */
1713 if( isLiteralSatisfied(scip, consdata, v) )
1714 continue;
1715
1716 violation = SCIPgetSolVal(scip, sol, var) - bounds[v];
1717
1718 /* if variable is continuous, then we cannot branch on one of the variable bounds */
1719 if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS ||
1720 ((SCIPisInfinity(scip, -varlb) || !SCIPisFeasEQ(scip, bounds[v], varlb)) &&
1721 (SCIPisInfinity(scip, varub) || !SCIPisFeasEQ(scip, bounds[v], varub))) )
1722 {
1723 SCIP_CALL( SCIPaddExternBranchCand(scip, var, REALABS(violation), bounds[v]) );
1724 *neednarybranch = FALSE;
1725 }
1726 *cutoff = FALSE;
1727 }
1728
1729 return SCIP_OKAY;
1730}
1731
1732/** enforces the pseudo or LP solution on the given constraint */
1733static
1735 SCIP* scip, /**< SCIP data structure */
1736 SCIP_CONS* cons, /**< bound disjunction constraint to be separated */
1737 SCIP_SOL* sol, /**< solution which should be enforced (NULL for LP solution) */
1738 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1739 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1740 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
1741 SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
1742 SCIP_Bool* registeredbrcand /**< pointer to store TRUE, if branching variable candidates were registered or was already true */
1743 )
1744{
1745 SCIP_Bool mustcheck;
1746 SCIP_Bool neednarybranch;
1747
1748 assert(cons != NULL);
1749 assert(SCIPconsGetHdlr(cons) != NULL);
1750 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1751 assert(cutoff != NULL);
1752 assert(infeasible != NULL);
1753 assert(reduceddom != NULL);
1754 assert(registeredbrcand != NULL);
1755
1756 SCIPdebugMsg(scip, "enforce bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
1757
1758 /* update and check the watched variables, if they were changed since last processing */
1760 {
1761 SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, infeasible, reduceddom, &mustcheck) );
1762 }
1763 else
1764 mustcheck = TRUE;
1765
1766 if( mustcheck )
1767 {
1768 if( isConsViolated(scip, cons, sol) )
1769 {
1770 /* constraint was infeasible -> reset age */
1772 *infeasible = TRUE;
1773
1774 /* register branching candidates */
1775 SCIP_CALL( registerBranchingCandidates(scip, cons, sol, cutoff, &neednarybranch) );
1776
1777 if( !neednarybranch )
1778 *registeredbrcand = TRUE;
1779 }
1780 }
1781
1782 return SCIP_OKAY;
1783}
1784
1785/** enforces a constraint by creating an n-ary branch consisting of a set of child nodes, each enforcing one literal
1786 */
1787static
1789 SCIP* scip, /**< SCIP data structure */
1790 SCIP_CONS* cons, /**< bound disjunction constraint to branch on */
1791 SCIP_SOL* sol /**< solution which should be enforced (NULL for LP solution) */
1792 )
1793{
1794 SCIP_CONSDATA* consdata;
1795 SCIP_VAR** vars;
1796 SCIP_BOUNDTYPE* boundtypes;
1797 SCIP_Real* bounds;
1798 SCIP_Real varlb;
1799 SCIP_Real varub;
1800 int nvars;
1801 int v;
1802
1803 SCIP_Real priority;
1804 SCIP_Real estimate;
1805 SCIP_NODE* node;
1806
1807 assert(cons != NULL);
1808 assert(SCIPconsGetHdlr(cons) != NULL);
1809 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1810
1811 consdata = SCIPconsGetData(cons);
1812 assert(consdata != NULL);
1813 nvars = consdata->nvars;
1814 vars = consdata->vars;
1815 boundtypes = consdata->boundtypes;
1816 bounds = consdata->bounds;
1817 assert(nvars == 0 || vars != NULL);
1818 assert(nvars == 0 || boundtypes != NULL);
1819 assert(nvars == 0 || bounds != NULL);
1820
1821 for( v = 0; v < nvars; ++v )
1822 {
1823 SCIP_VAR* var;
1824
1825 var = vars[v];
1826 assert(var != NULL);
1827
1828 /* constraint should be violated, so all bounds in the constraint have to be violated */
1829 assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPgetSolVal(scip, sol, var), bounds[v])) && /*lint !e666*/
1830 !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPgetSolVal(scip, sol, var), bounds[v])) ); /*lint !e666*/
1831
1832 varlb = SCIPcomputeVarLbLocal(scip, var);
1833 varub = SCIPcomputeVarUbLocal(scip, var);
1834
1835 /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied,
1836 * thus there is no use in creating an extra child for it
1837 */
1838 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) )
1839 continue;
1840 /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied,
1841 * thus there is no use in creating an extra child for it
1842 */
1843 if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) )
1844 continue;
1845 /* if literal is always satisfied, then no need to branch on it */
1846 if( isLiteralSatisfied(scip, consdata, v) )
1847 continue;
1848
1849 /* create a child that enforces the current literal */
1850 priority = SCIPcalcNodeselPriority(scip, var, boundtypes[v] == SCIP_BOUNDTYPE_LOWER ?
1852 estimate = SCIPcalcChildEstimate (scip, var, bounds[v]);
1853
1854 SCIPdebugMsg(scip, " -> creating child to enforce: <%s> %c= %g (priority: %g, estimate: %g)\n",
1855 SCIPvarGetName(vars[v]), boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<', bounds[v], priority, estimate);
1856
1857 SCIP_CALL( SCIPcreateChild(scip, &node, priority, estimate) );
1858
1859 /* enforce current literal */
1861 {
1862 SCIP_CONS* brcons;
1863 SCIP_Real one;
1864
1865 one = 1.0;
1866
1867 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1868 {
1869 SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, bounds[v], SCIPinfinity(scip),
1873 SCIPconsIsStickingAtNode(cons)) );
1874 }
1875 else
1876 {
1877 SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, -SCIPinfinity(scip), bounds[v],
1881 SCIPconsIsStickingAtNode(cons)) );
1882 }
1883 SCIP_CALL( SCIPaddConsNode(scip, node, brcons, NULL) );
1884 SCIP_CALL( SCIPreleaseCons(scip, &brcons) );
1885 }
1886 else
1887 {
1888 assert(SCIPvarIsActive(var));
1889 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1890 {
1891 SCIP_CALL( SCIPchgVarLbNode(scip, node, var, bounds[v]) );
1892 }
1893 else
1894 {
1895 SCIP_CALL( SCIPchgVarUbNode(scip, node, var, bounds[v]) );
1896 }
1897 }
1898
1899 /* delete bound disjunction constraint from child node */
1900 SCIP_CALL( SCIPdelConsNode(scip, node, cons) );
1901 }
1902
1903 return SCIP_OKAY;
1904}
1905
1906/** helper function to enforce constraints */
1907static
1909 SCIP* scip, /**< SCIP data structure */
1910 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1911 SCIP_CONS** conss, /**< constraints to process */
1912 int nconss, /**< number of constraints */
1913 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
1914 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
1915 )
1916{
1917 SCIP_CONSHDLRDATA* conshdlrdata;
1918 SCIP_Bool cutoff;
1919 SCIP_Bool infeasible;
1920 SCIP_Bool reduceddom;
1921 SCIP_Bool registeredbrcand;
1922 SCIP_Bool infeasiblecons;
1923 int c;
1924 int nnarybranchconsvars;
1925 SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */
1926
1927 assert(conshdlr != NULL);
1928 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1929 assert(nconss == 0 || conss != NULL);
1930 assert(result != NULL);
1931
1932 SCIPdebugMsg(scip, "Enforcing %d bound disjunction constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation");
1933
1934 *result = SCIP_FEASIBLE;
1935
1936 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1937 assert(conshdlrdata != NULL);
1938
1939 cutoff = FALSE;
1940 infeasible = FALSE;
1941 reduceddom = FALSE;
1942 registeredbrcand = FALSE;
1943 narybranchcons = NULL;
1944 nnarybranchconsvars = INT_MAX;
1945
1946 /* check all bound disjunction constraints for feasibility */
1947 for( c = 0; c < nconss && !cutoff && !reduceddom; ++c )
1948 {
1949 infeasiblecons = FALSE;
1950 SCIP_CALL( enforceCurrentSol(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &infeasiblecons, &reduceddom,
1951 &registeredbrcand) );
1952 infeasible |= infeasiblecons;
1953 if( infeasiblecons && !registeredbrcand )
1954 {
1955 /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */
1956 if( narybranchcons == NULL || SCIPconsGetData(conss[c])->nvars < nnarybranchconsvars )
1957 {
1958 narybranchcons = conss[c];
1959 nnarybranchconsvars = SCIPconsGetData(narybranchcons)->nvars;
1960 assert(nnarybranchconsvars > 0);
1961 }
1962 }
1963 }
1964
1965 if( cutoff )
1966 *result = SCIP_CUTOFF;
1967 else if( reduceddom )
1968 *result = SCIP_REDUCEDDOM;
1969 else if( infeasible )
1970 {
1971 if( registeredbrcand )
1972 {
1973 *result = SCIP_INFEASIBLE;
1974 }
1975 else
1976 {
1977 SCIP_CALL( createNAryBranch(scip, narybranchcons, sol) );
1978 *result = SCIP_BRANCHED;
1979 }
1980 }
1981
1982 return SCIP_OKAY;
1983}
1984
1985/** adds symmetry information of constraint to a symmetry detection graph */
1986static
1988 SCIP* scip, /**< SCIP pointer */
1989 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */
1990 SCIP_CONS* cons, /**< constraint */
1991 SYM_GRAPH* graph, /**< symmetry detection graph */
1992 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */
1993 )
1994{
1995 SCIP_CONSDATA* consdata;
1996 SCIP_VAR** vars;
1997 SCIP_Real* vals;
1998 SCIP_Real constant;
1999 SCIP_Real bound = 0.0;
2000 int consnodeidx;
2001 int opnodeidx;
2002 int nodeidx;
2003 int nconsvars;
2004 int nlocvars;
2005 int nvars;
2006 int i;
2007
2008 assert(scip != NULL);
2009 assert(cons != NULL);
2010 assert(graph != NULL);
2011 assert(success != NULL);
2012
2013 *success = TRUE;
2014
2015 consdata = SCIPconsGetData(cons);
2016 assert(consdata != NULL);
2017
2018 /* add node initializing constraint (with artificial rhs) */
2019 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &consnodeidx) );
2020
2021 /* create nodes and edges for each literal in the bounddisjunction */
2022 nvars = SCIPgetNVars(scip);
2023 nconsvars = consdata->nvars;
2024
2025 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2026 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
2027
2028 for( i = 0; i < nconsvars; ++i )
2029 {
2030 /* add node and edge for bound expression of literal */
2031 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_BDDISJ, &opnodeidx) ); /*lint !e641*/
2032 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, opnodeidx, FALSE, 0.0) );
2033
2034 /* get active variables */
2035 vars[0] = consdata->vars[i];
2036 vals[0] = consdata->boundtypes[i] == SCIP_BOUNDTYPE_UPPER ? 1.0 : -1.0;
2037 nlocvars = 1;
2038 constant = 0.0;
2039
2040 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant,
2042
2043 /* add node and edge for bound on literal (bound adapted by constant) */
2044 bound = consdata->boundtypes[i] == SCIP_BOUNDTYPE_UPPER ? consdata->bounds[i] : -consdata->bounds[i];
2045 bound -= constant;
2046
2047 SCIP_CALL( SCIPaddSymgraphValnode(scip, graph, bound, &nodeidx) );
2048 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) );
2049
2050 /* check whether variable is (multi-)aggregated */
2051 nodeidx = opnodeidx;
2052 if( nlocvars > 1 )
2053 {
2054 /* encode aggregation by a sum-expression and connect it to bdexpr node */
2055 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int) SYM_CONSOPTYPE_SUM, &nodeidx) ); /*lint !e641*/
2056 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, opnodeidx, nodeidx, FALSE, 0.0) );
2057 }
2058
2059 /* add nodes and edges for variables in aggregation (ignore constant, has been treated above) */
2060 SCIP_CALL( SCIPaddSymgraphVarAggregation(scip, graph, nodeidx, vars, vals, nlocvars, 0.0) );
2061 }
2062
2063 SCIPfreeBufferArray(scip, &vals);
2064 SCIPfreeBufferArray(scip, &vars);
2065
2066 return SCIP_OKAY;
2067}
2068
2069/**@} */
2070
2071/**@name Callback methods of constraint handler
2072 *
2073 * @{
2074 */
2075
2076/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2077static
2078SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBounddisjunction)
2079{ /*lint --e{715}*/
2080 assert(scip != NULL);
2081 assert(conshdlr != NULL);
2082 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2083
2084 /* call inclusion method of constraint handler */
2086
2087 *valid = TRUE;
2088
2089 return SCIP_OKAY;
2090}
2091
2092/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
2093static
2094SCIP_DECL_CONSFREE(consFreeBounddisjunction)
2095{ /*lint --e{715}*/
2096 SCIP_CONSHDLRDATA* conshdlrdata;
2097
2098 assert(conshdlr != NULL);
2099 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2100 assert(scip != NULL);
2101
2102 /* free constraint handler data */
2103 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2104 assert(conshdlrdata != NULL);
2105
2106 conshdlrdataFree(scip, &conshdlrdata);
2107
2108 SCIPconshdlrSetData(conshdlr, NULL);
2109
2110 return SCIP_OKAY;
2111}
2112
2113
2114/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
2115static
2116SCIP_DECL_CONSEXITPRE(consExitpreBounddisjunction)
2117{ /*lint --e{715}*/
2118 SCIP_CONSHDLRDATA* conshdlrdata;
2119 SCIP_CONS* cons;
2120 SCIP_Bool redundant;
2121 int c;
2122
2123 assert(conshdlr != NULL);
2124 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2125 assert(scip != NULL);
2126
2127 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2128 assert(conshdlrdata != NULL);
2129
2130 /* fast processing of constraints, apply global bounds and remove fixed variables */
2131 for( c = 0; c < nconss; ++c )
2132 {
2133 cons = conss[c];
2134 assert(cons != NULL);
2135
2136 SCIPdebugMsg(scip, "exit-presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2137
2138 if( SCIPconsIsDeleted(cons) )
2139 continue;
2140
2141 /* remove all literals that are violated in global bounds, check redundancy due to global bounds */
2142 SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2143
2144 if( !redundant )
2145 {
2146 /* replace variables by their representative active (or multi-aggregated) variables */
2147 SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2148 }
2149
2150 if( redundant && SCIPconsIsAdded(cons) )
2151 {
2152 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons));
2153 SCIP_CALL( SCIPdelCons(scip, cons) );
2154 }
2155 }
2156
2157 return SCIP_OKAY;
2158}
2159
2160/** solving process initialization method of constraint handler */
2161static
2162SCIP_DECL_CONSINITSOL(consInitsolBounddisjunction)
2163{ /*lint --e{715}*/
2164 /* add nlrow representation to NLP, if NLP had been constructed and disjunction is simple enough */
2166 {
2167 SCIP_CONSDATA* consdata;
2168 SCIP_NLROW* nlrow;
2169 SCIP_EXPR* expr;
2170 SCIP_EXPR* exprvar;
2171 SCIP_Real lincoef;
2172 SCIP_Real a, b;
2173 int c;
2174
2175 for( c = 0; c < nconss; ++c )
2176 {
2177 /* skip deactivated or redundant constraints */
2178 if( !SCIPconsIsActive(conss[c]) || !SCIPconsIsChecked(conss[c]) )
2179 return SCIP_OKAY;
2180
2181 assert(!SCIPconsIsLocal(conss[c])); /* we are at the root node (or short before) */
2182
2183 consdata = SCIPconsGetData(conss[c]);
2184 assert(consdata != NULL);
2185
2186 /* look for a bounddisjunction of the form
2187 * x <= a or x >= b with a < b
2188 * only one of the inequalities can be strictly satisfied, so we can reformulate as
2189 * (x-a)*(b-x) <= 0
2190 * this should be sufficient to get bounddisjunction constraints that represent semi-continuous variables into the NLP
2191 */
2192
2193 if( consdata->nvars != 2 )
2194 continue;
2195
2196 if( consdata->vars[0] != consdata->vars[1] )
2197 continue;
2198
2199 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_UPPER && consdata->boundtypes[1] == SCIP_BOUNDTYPE_LOWER )
2200 {
2201 a = consdata->bounds[0];
2202 b = consdata->bounds[1];
2203 }
2204 else if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER && consdata->boundtypes[1] == SCIP_BOUNDTYPE_UPPER )
2205 {
2206 a = consdata->bounds[1];
2207 b = consdata->bounds[0];
2208 }
2209 else
2210 {
2211 continue;
2212 }
2213
2214 if( a >= b )
2215 continue;
2216
2217 SCIP_CALL( SCIPcreateExprVar(scip, &exprvar, consdata->vars[0], NULL, NULL) );
2218 SCIP_CALL( SCIPcreateExprPow(scip, &expr, exprvar, 2.0, NULL, NULL) );
2219
2220 /* add xb-xx-ab+ax <= 0 as -ab <= -(a+b)x + x^2 */
2221 lincoef = -a - b;
2222 SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[c]),
2223 0.0, 1, consdata->vars, &lincoef, expr, -a*b, SCIPinfinity(scip), SCIP_EXPRCURV_CONVEX) );
2224
2225 SCIP_CALL( SCIPreleaseExpr(scip, &expr) );
2226 SCIP_CALL( SCIPreleaseExpr(scip, &exprvar) );
2227
2228 SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
2229 SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
2230 }
2231 }
2232
2233 return SCIP_OKAY;
2234}
2235
2236/** frees specific constraint data */
2237static
2238SCIP_DECL_CONSDELETE(consDeleteBounddisjunction)
2239{ /*lint --e{715}*/
2240 assert(conshdlr != NULL);
2241 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2242 assert(consdata != NULL);
2243 assert(*consdata != NULL);
2244
2245 /* free LP row and bound disjunction constraint */
2246 consdataFree(scip, consdata);
2247
2248 return SCIP_OKAY;
2249}
2250
2251
2252/** transforms constraint data into data belonging to the transformed problem */
2253static
2254SCIP_DECL_CONSTRANS(consTransBounddisjunction)
2255{ /*lint --e{715}*/
2256 SCIP_CONSDATA* sourcedata;
2257 SCIP_CONSDATA* targetdata;
2258
2259 /*debugMsg(scip, "Trans method of bound disjunction constraints\n");*/
2260
2261 assert(conshdlr != NULL);
2262 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2264 assert(sourcecons != NULL);
2265 assert(targetcons != NULL);
2266
2267 sourcedata = SCIPconsGetData(sourcecons);
2268 assert(sourcedata != NULL);
2269
2270 /* create constraint data for target constraint */
2271 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->nvars, sourcedata->vars,
2272 sourcedata->boundtypes, sourcedata->bounds) );
2273
2274 /* create target constraint */
2275 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2276 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2277 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2278 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2279 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2280
2281 return SCIP_OKAY;
2282}
2283
2284
2285/** constraint enforcing method of constraint handler for LP solutions */
2286static
2287SCIP_DECL_CONSENFOLP(consEnfolpBounddisjunction)
2288{ /*lint --e{715}*/
2289 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
2290
2291 return SCIP_OKAY;
2292}
2293
2294
2295/** constraint enforcing method of constraint handler for relaxation solutions */
2296static
2297SCIP_DECL_CONSENFORELAX(consEnforelaxBounddisjunction)
2298{ /*lint --e{715}*/
2299 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
2300
2301 return SCIP_OKAY;
2302}
2303
2304
2305/** constraint enforcing method of constraint handler for pseudo solutions */
2306static
2307SCIP_DECL_CONSENFOPS(consEnfopsBounddisjunction)
2308{ /*lint --e{715}*/
2309 SCIP_CONSHDLRDATA* conshdlrdata;
2310 SCIP_Bool cutoff;
2311 SCIP_Bool infeasible;
2312 SCIP_Bool reduceddom;
2313 SCIP_Bool registeredbrcand;
2314 int c;
2315 SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */
2316
2317 assert(conshdlr != NULL);
2318 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2319 assert(nconss == 0 || conss != NULL);
2320 assert(result != NULL);
2321
2322 SCIPdebugMsg(scip, "pseudo enforcing %d bound disjunction constraints\n", nconss);
2323
2324 *result = SCIP_FEASIBLE;
2325
2326 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2327 assert(conshdlrdata != NULL);
2328
2329 cutoff = FALSE;
2330 infeasible = FALSE;
2331 reduceddom = FALSE;
2332 registeredbrcand = FALSE;
2333 narybranchcons = NULL;
2334
2335 /* check all bound disjunction constraints for feasibility */
2336 for( c = 0; c < nconss && !cutoff && !reduceddom; ++c )
2337 {
2338 SCIP_CALL( enforceCurrentSol(scip, conss[c], NULL, conshdlrdata->eventhdlr, &cutoff, &infeasible, &reduceddom,
2339 &registeredbrcand) );
2340 if( infeasible && !registeredbrcand )
2341 {
2342 /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */
2343 if( !narybranchcons || SCIPconsGetData(conss[c])->nvars < SCIPconsGetData(narybranchcons)->nvars )
2344 narybranchcons = conss[c];
2345 }
2346 }
2347
2348 if( cutoff )
2349 *result = SCIP_CUTOFF;
2350 else if( reduceddom )
2351 *result = SCIP_REDUCEDDOM;
2352 else if( infeasible )
2353 {
2354 if( registeredbrcand )
2355 {
2356 *result = SCIP_INFEASIBLE;
2357 }
2358 else
2359 {
2360 SCIP_CALL( createNAryBranch(scip, narybranchcons, NULL) );
2361 *result = SCIP_BRANCHED;
2362 }
2363 }
2364
2365 return SCIP_OKAY;
2366}
2367
2368
2369/** feasibility check method of constraint handler for integral solutions */
2370static
2371SCIP_DECL_CONSCHECK(consCheckBounddisjunction)
2372{ /*lint --e{715}*/
2373 SCIP_CONS* cons;
2374 SCIP_CONSDATA* consdata;
2375 int c;
2376
2377 assert(conshdlr != NULL);
2378 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2379 assert(nconss == 0 || conss != NULL);
2380 assert(result != NULL);
2381
2382 *result = SCIP_FEASIBLE;
2383
2384 /* check all bound disjunction constraints for feasibility */
2385 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
2386 {
2387 cons = conss[c];
2388 consdata = SCIPconsGetData(cons);
2389 assert(consdata != NULL);
2390
2391 if( isConsViolated(scip, cons, sol) )
2392 {
2393 if( printreason )
2394 {
2395 int v;
2396
2397 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2398 SCIPinfoMessage(scip, NULL, ";\nviolation: ");
2399 for( v = 0; v < consdata->nvars; ++v )
2400 {
2401 assert(consdata->vars[v] != NULL);
2402 if( v > 0 )
2403 SCIPinfoMessage(scip, NULL, ", ");
2404 SCIPinfoMessage(scip, NULL, "<%s> = %.15g",
2405 SCIPvarGetName(consdata->vars[v]), SCIPgetSolVal(scip, sol, consdata->vars[v]));
2406 }
2407 SCIPinfoMessage(scip, NULL, ")\n");
2408 }
2409
2410 /* constraint is violated */
2411 *result = SCIP_INFEASIBLE;
2412 }
2413 }
2414
2415 return SCIP_OKAY;
2416}
2417
2418
2419/** domain propagation method of constraint handler */
2420static
2421SCIP_DECL_CONSPROP(consPropBounddisjunction)
2422{ /*lint --e{715}*/
2423 SCIP_CONSHDLRDATA* conshdlrdata;
2424 SCIP_Bool cutoff;
2425 SCIP_Bool infeasible;
2426 SCIP_Bool reduceddom;
2427 SCIP_Bool mustcheck;
2428 SCIP_Bool consreduceddom;
2429 int c;
2430
2431 assert(conshdlr != NULL);
2432 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2433 assert(nconss == 0 || conss != NULL);
2434 assert(result != NULL);
2435
2436 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2437 assert(conshdlrdata != NULL);
2438
2439 cutoff = FALSE;
2440 infeasible = FALSE;
2441 reduceddom = FALSE;
2442
2443 /* propagate all useful bound disjunction constraints */
2444 for( c = 0; c < nusefulconss && !cutoff; ++c )
2445 {
2446 SCIP_CALL( processWatchedVars(scip, conss[c], conshdlrdata->eventhdlr,
2447 &cutoff, &infeasible, &consreduceddom, &mustcheck) );
2448 reduceddom = reduceddom || consreduceddom;
2449 }
2450
2451 /* return the correct result */
2452 if( cutoff )
2453 *result = SCIP_CUTOFF;
2454 else if( reduceddom )
2455 *result = SCIP_REDUCEDDOM;
2456 else
2457 *result = SCIP_DIDNOTFIND;
2458
2459 return SCIP_OKAY; /*lint !e438*/
2460}
2461
2462
2463/** presolving method of constraint handler */
2464static
2465SCIP_DECL_CONSPRESOL(consPresolBounddisjunction)
2466{ /*lint --e{715}*/
2467 SCIP_CONSHDLRDATA* conshdlrdata;
2468 SCIP_CONS* cons;
2469 SCIP_CONSDATA* consdata;
2470 SCIP_Bool infeasible;
2471 SCIP_Bool redundant;
2472 SCIP_Bool tightened;
2473 int c;
2474
2475 assert(conshdlr != NULL);
2476 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2477 assert(scip != NULL);
2478 assert(result != NULL);
2479
2480 *result = SCIP_DIDNOTFIND;
2481
2482 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2483 assert(conshdlrdata != NULL);
2484
2485 /* process constraints */
2486 for( c = 0; c < nconss && *result != SCIP_CUTOFF && !SCIPisStopped(scip); ++c )
2487 {
2488 cons = conss[c];
2489 assert(cons != NULL);
2490 consdata = SCIPconsGetData(cons);
2491 assert(consdata != NULL);
2492
2493 SCIPdebugMsg(scip, "presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2494
2495 /* force presolving the constraint in the initial round */
2496 if( nrounds == 0 )
2497 {
2499 }
2500
2501 /* remove all literals that are violated in global bounds, check redundancy due to global bounds */
2502 SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2503
2504 if( !redundant )
2505 {
2506 /* replace variables by their representative active (or multi-aggregated) variables */
2507 SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2508 }
2509
2510 /**@todo find pairs of negated variables in constraint: constraint is redundant */
2511 /**@todo find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
2512
2513 if( redundant )
2514 {
2515 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons));
2516 SCIP_CALL( SCIPdelCons(scip, cons) );
2517 (*ndelconss)++;
2518 *result = SCIP_SUCCESS;
2519 continue;
2520 }
2521 else if( !SCIPconsIsModifiable(cons) )
2522 {
2523 /* if unmodifiable constraint has no variables, it is infeasible,
2524 * if unmodifiable constraint has only one variable, the literal can be satisfied and the constraint deleted
2525 */
2526 if( consdata->nvars == 0 )
2527 {
2528 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2529 *result = SCIP_CUTOFF;
2530 return SCIP_OKAY;
2531 }
2532 else if( consdata->nvars == 1 )
2533 {
2534 SCIPdebugMsg(scip, "bound disjunction constraint <%s> has only one undecided literal\n",
2535 SCIPconsGetName(cons));
2536
2537 assert(consdata->vars != NULL);
2538 assert(!isLiteralSatisfied(scip, consdata, 0));
2539 assert(!isLiteralViolated(scip, consdata, 0));
2540
2541 if( SCIPvarIsActive(consdata->vars[0]) )
2542 {
2543 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER )
2544 {
2545 SCIP_CALL( SCIPtightenVarLb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) );
2546 }
2547 else
2548 {
2549 SCIP_CALL( SCIPtightenVarUb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) );
2550 }
2551 if( infeasible )
2552 {
2553 SCIPdebugMsg(scip, " -> infeasible fixing\n");
2554 *result = SCIP_CUTOFF;
2555 return SCIP_OKAY;
2556 }
2557 assert(tightened);
2558 (*nchgbds)++;
2559 }
2560 else
2561 {
2562 /* upgrade to a linear constraint, if vars[0] is multi-aggregated */
2563 SCIP_CONS* lincons;
2564 SCIP_Real one;
2565
2566 assert(SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_MULTAGGR);
2567
2568 one = 1.0;
2569 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER )
2570 {
2572 1, &consdata->vars[0], &one, consdata->bounds[0], SCIPinfinity(scip),
2576 SCIPconsIsStickingAtNode(cons)) );
2577 }
2578 else
2579 {
2581 1, &consdata->vars[0], &one, -SCIPinfinity(scip), consdata->bounds[0],
2585 SCIPconsIsStickingAtNode(cons)) );
2586 }
2587 SCIP_CALL( SCIPaddCons(scip, lincons) );
2588 SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
2589 (*nupgdconss)++;
2590 }
2591
2592 SCIP_CALL( SCIPdelCons(scip, cons) );
2593 (*ndelconss)++;
2594 *result = SCIP_SUCCESS;
2595 continue;
2596 }
2597 else
2598 {
2599 /* try to upgrade the bounddisjunction constraint */
2600 SCIP_CALL( upgradeCons(scip, cons, ndelconss, naddconss) );
2601 }
2602 }
2603 }
2604
2605 /**@todo preprocess pairs of bound disjunction constraints */
2606
2607 return SCIP_OKAY;
2608}
2609
2610
2611/** propagation conflict resolving method of constraint handler */
2612static
2613SCIP_DECL_CONSRESPROP(consRespropBounddisjunction)
2614{ /*lint --e{715}*/
2615 SCIP_CONSDATA* consdata;
2616 SCIP_VAR** vars;
2617 SCIP_BOUNDTYPE* boundtypes;
2618#ifndef NDEBUG
2619 SCIP_Real* bounds;
2620#endif
2621 int v;
2622
2623 assert(conshdlr != NULL);
2624 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2625 assert(cons != NULL);
2626 assert(infervar != NULL);
2627 assert(result != NULL);
2628
2629 consdata = SCIPconsGetData(cons);
2630 assert(consdata != NULL);
2631 assert(consdata->vars != NULL);
2632 assert(consdata->nvars > 0);
2633 assert(0 <= inferinfo && inferinfo < consdata->nvars);
2634 assert(consdata->vars[inferinfo] == infervar);
2635
2636 vars = consdata->vars;
2637 boundtypes = consdata->boundtypes;
2638#ifndef NDEBUG
2639 bounds = consdata->bounds;
2640 assert(bounds != NULL);
2641#endif
2642 assert(boundtypes != NULL);
2643
2644 SCIPdebugMsg(scip, "conflict resolving method of bound disjunction constraint handler\n");
2645
2646 /* the only deductions are bounds tightened to a literal's bound on bound disjunction constraints where all other
2647 * literals are violated
2648 */
2649 assert((boundtypes[inferinfo] == SCIP_BOUNDTYPE_LOWER
2650 && SCIPisFeasGE(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), bounds[inferinfo]))
2651 || (boundtypes[inferinfo] == SCIP_BOUNDTYPE_UPPER
2652 && SCIPisFeasLE(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE), bounds[inferinfo])));
2653
2654 for( v = 0; v < consdata->nvars; ++v )
2655 {
2656 if( v != inferinfo )
2657 {
2658 assert(consdata->vars[v] != infervar || consdata->boundtypes[v] != consdata->boundtypes[inferinfo]);
2659
2660 /* the reason literal must have been violated
2661 * we do not check for multi-aggregated variables, since SCIPvarGetXbAtIndex is not implemented for them */
2662 /* Use a weaker comparison to SCIPvarGetXbAtIndex here (i.e., SCIPisXT instead of SCIPisFeasXT),
2663 * because SCIPvarGetXbAtIndex might differ from the local bound at time bdchgidx by epsilon. */
2664 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_MULTAGGR
2665 || (boundtypes[v] == SCIP_BOUNDTYPE_LOWER
2666 && SCIPisLT(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, TRUE), bounds[v]))
2667 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER
2668 && SCIPisGT(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, TRUE), bounds[v])));
2669 SCIP_CALL( SCIPaddConflictBd(scip, vars[v], SCIPboundtypeOpposite(boundtypes[v]), bdchgidx) );
2670 }
2671 }
2672
2673 *result = SCIP_SUCCESS;
2674
2675 return SCIP_OKAY;
2676}
2677
2678
2679/** variable rounding lock method of constraint handler */
2680static
2681SCIP_DECL_CONSLOCK(consLockBounddisjunction)
2682{ /*lint --e{715}*/
2683 SCIP_CONSDATA* consdata;
2684 int i;
2685
2686 consdata = SCIPconsGetData(cons);
2687 assert(consdata != NULL);
2688
2689 /* lock every single coefficient */
2690 for( i = 0; i < consdata->nvars; ++i )
2691 {
2692 if( consdata->boundtypes[i] == SCIP_BOUNDTYPE_LOWER )
2693 {
2694 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos, nlocksneg) );
2695 }
2696 else
2697 {
2698 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlocksneg, nlockspos) );
2699 }
2700 }
2701
2702 return SCIP_OKAY;
2703}
2704
2705
2706/** constraint activation notification method of constraint handler */
2707static
2708SCIP_DECL_CONSACTIVE(consActiveBounddisjunction)
2709{ /*lint --e{715}*/
2710 SCIP_CONSHDLRDATA* conshdlrdata;
2711 SCIP_CONSDATA* consdata;
2712
2713 assert(conshdlr != NULL);
2714 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2715 assert(cons != NULL);
2716 assert(SCIPconsIsTransformed(cons));
2717
2718 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2719 assert(conshdlrdata != NULL);
2720 consdata = SCIPconsGetData(cons);
2721 assert(consdata != NULL);
2722 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
2723
2724 SCIPdebugMsg(scip, "activating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2725 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
2726
2727 /* catch events on watched variables */
2728 if( consdata->watchedvar1 != -1 )
2729 {
2730 SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1,
2731 &consdata->filterpos1) );
2732 }
2733 if( consdata->watchedvar2 != -1 )
2734 {
2735 SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2,
2736 &consdata->filterpos2) );
2737 }
2738
2739 return SCIP_OKAY;
2740}
2741
2742
2743/** constraint deactivation notification method of constraint handler */
2744static
2745SCIP_DECL_CONSDEACTIVE(consDeactiveBounddisjunction)
2746{ /*lint --e{715}*/
2747 SCIP_CONSHDLRDATA* conshdlrdata;
2748 SCIP_CONSDATA* consdata;
2749
2750 assert(conshdlr != NULL);
2751 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2752 assert(cons != NULL);
2753 assert(SCIPconsIsTransformed(cons));
2754
2755 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2756 assert(conshdlrdata != NULL);
2757 consdata = SCIPconsGetData(cons);
2758 assert(consdata != NULL);
2759 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
2760
2761 SCIPdebugMsg(scip, "deactivating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2762 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
2763
2764 /* drop events on watched variables */
2765 if( consdata->watchedvar1 != -1 )
2766 {
2767 assert(consdata->filterpos1 != -1);
2768 SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
2769 consdata->watchedvar1 = -1;
2770 }
2771 if( consdata->watchedvar2 != -1 )
2772 {
2773 assert(consdata->filterpos2 != -1);
2774 SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
2775 consdata->watchedvar2 = -1;
2776 }
2777
2778 return SCIP_OKAY;
2779}
2780
2781
2782/** constraint display method of constraint handler */
2783static
2784SCIP_DECL_CONSPRINT(consPrintBounddisjunction)
2785{ /*lint --e{715}*/
2786 assert( scip != NULL );
2787 assert( conshdlr != NULL );
2788 assert( cons != NULL );
2789
2790 consdataPrint(scip, SCIPconsGetData(cons), file, FALSE);
2791
2792 return SCIP_OKAY;
2793}
2794
2795/** constraint copying method of constraint handler */
2796static
2797SCIP_DECL_CONSCOPY(consCopyBounddisjunction)
2798{ /*lint --e{715}*/
2799 SCIP_VAR** sourcevars;
2800 SCIP_VAR** targetvars;
2801 SCIP_BOUNDTYPE* boundtypes;
2802 SCIP_Real* bounds;
2803 int nvars;
2804 int v;
2805
2806 assert(valid != NULL);
2807
2808 *valid = TRUE;
2809
2810 /* get source data */
2811 sourcevars = SCIPgetVarsBounddisjunction(sourcescip, sourcecons);
2812 nvars = SCIPgetNVarsBounddisjunction(sourcescip, sourcecons);
2813 boundtypes = SCIPgetBoundtypesBounddisjunction(sourcescip, sourcecons);
2814 bounds = SCIPgetBoundsBounddisjunction(sourcescip, sourcecons);
2815
2816 SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, nvars) );
2817
2818 /* map source variables to active variables of the target SCIP */
2819 for( v = 0; v < nvars && *valid; ++v )
2820 {
2821 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) );
2822 assert(!(*valid) || targetvars[v] != NULL);
2823 }
2824
2825 /* only create the target constraint, if all variables could be copied */
2826 if( *valid )
2827 {
2828 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name ? name : SCIPconsGetName(sourcecons), nvars, targetvars, boundtypes,
2829 bounds, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2830 }
2831
2832 SCIPfreeBufferArray(scip, &targetvars);
2833
2834 return SCIP_OKAY;
2835}
2836
2837/** constraint parsing method of constraint handler */
2838static
2839SCIP_DECL_CONSPARSE(consParseBounddisjunction)
2840{ /*lint --e{715}*/
2841 SCIP_BOUNDTYPE* boundtypes;
2842 SCIP_Real* bounds;
2843 SCIP_VAR** vars;
2844 char* endptr;
2845 int varssize;
2846 int nvars;
2847
2848 assert( success != NULL );
2849 *success = TRUE;
2850
2851 SCIPdebugMsg(scip, "parse <%s> as bounddisjunction constraint\n", str);
2852
2853 /* skip white space */
2854 SCIP_CALL( SCIPskipSpace((char**)&str) );
2855
2856 /* check for string "bounddisjunction" */
2857 if( strncmp(str, "bounddisjunction(", 16) != 0 )
2858 {
2859 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "error during parsing: expected \"bounddisjunction(\" in <%s>.\n", str);
2860 *success = FALSE;
2861 return SCIP_OKAY;
2862 }
2863
2864 /* skip "bounddisjunction(" */
2865 str += 17;
2866
2867 varssize = 100;
2868 nvars = 0;
2869
2870 /* allocate buffer array for variables */
2871 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
2872 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, varssize) );
2873 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, varssize) );
2874
2875 /* parse string until ")" */
2876 while( *str != ')' )
2877 {
2878 SCIP_VAR* var;
2879
2880 /* parse variable name */
2881 SCIP_CALL( SCIPparseVarName(scip, str, &var, &endptr) );
2882
2883 if( var == NULL )
2884 {
2885 endptr = strchr(endptr, ')');
2886
2887 if( endptr == NULL )
2888 {
2889 *success = FALSE;
2890 goto TERMINATE;
2891 }
2892
2893 break;
2894 }
2895
2896 str = endptr;
2897
2898 /* skip white space */
2899 SCIP_CALL( SCIPskipSpace((char**)&str) );
2900
2901 /* parse bound type */
2902 switch( *str )
2903 {
2904 case '<':
2905 boundtypes[nvars] = SCIP_BOUNDTYPE_UPPER;
2906 break;
2907 case '>':
2908 boundtypes[nvars] = SCIP_BOUNDTYPE_LOWER;
2909 break;
2910 default:
2911 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variable with name <%s> does not exist\n", SCIPvarGetName(var));
2912 *success = FALSE;
2913 goto TERMINATE;
2914 }
2915
2916 ++str;
2917 if( *str != '=' )
2918 {
2919 SCIPdebugMsg(scip, "expected '=': %s\n", str);
2920 *success = FALSE;
2921 goto TERMINATE;
2922 }
2923
2924 /* skip '=' */
2925 ++str;
2926
2927 /* parse bound value */
2928 if( !SCIPparseReal(scip, str, &bounds[nvars], &endptr) )
2929 {
2930 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error during parsing of the weight: %s\n", str);
2931 *success = FALSE;
2932 goto TERMINATE;
2933 }
2934
2935 str = endptr;
2936
2937 /* set variable */
2938 vars[nvars++] = var;
2939
2940 /* check if the size of the variable array was big enough */
2941 if( nvars > varssize )
2942 {
2943 /* reallocate memory */
2944 varssize *= 2;
2945 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
2946 SCIP_CALL( SCIPreallocBufferArray(scip, &boundtypes, varssize) );
2947 SCIP_CALL( SCIPreallocBufferArray(scip, &bounds, varssize) );
2948 }
2949
2950 /* skip white space */
2951 SCIP_CALL( SCIPskipSpace((char**)&str) );
2952
2953 /* skip ',' */
2954 if( *str == ',' )
2955 ++str;
2956 }
2957
2958 /* add bounddisjunction */
2959 if( *success && nvars > 0 )
2960 {
2961 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds,
2962 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2963 }
2964
2965 TERMINATE:
2966 /* free variable buffer */
2967 SCIPfreeBufferArray(scip, &bounds);
2968 SCIPfreeBufferArray(scip, &boundtypes);
2969 SCIPfreeBufferArray(scip, &vars);
2970
2971 return SCIP_OKAY;
2972}
2973
2974/** constraint method of constraint handler which returns the variables (if possible) */
2975static
2976SCIP_DECL_CONSGETVARS(consGetVarsBounddisjunction)
2977{ /*lint --e{715}*/
2978 SCIP_CONSDATA* consdata;
2979
2980 assert(cons != NULL);
2981
2982 consdata = SCIPconsGetData(cons);
2983 assert(consdata != NULL);
2984
2985 if( varssize < consdata->nvars )
2986 (*success) = FALSE;
2987 else
2988 {
2989 assert(vars != NULL);
2990
2991 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
2992 (*success) = TRUE;
2993 }
2994
2995 return SCIP_OKAY;
2996}
2997
2998/** constraint method of constraint handler which returns the number of variables (if possible) */
2999static
3000SCIP_DECL_CONSGETNVARS(consGetNVarsBounddisjunction)
3001{ /*lint --e{715}*/
3002 SCIP_CONSDATA* consdata;
3003
3004 assert(cons != NULL);
3005
3006 consdata = SCIPconsGetData(cons);
3007 assert(consdata != NULL);
3008
3009 (*nvars) = consdata->nvars;
3010 (*success) = TRUE;
3011
3012 return SCIP_OKAY;
3013}
3014
3015/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
3016static
3017SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphBounddisjunction)
3018{ /*lint --e{715}*/
3019 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) );
3020
3021 return SCIP_OKAY;
3022}
3023
3024/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
3025static
3026SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphBounddisjunction)
3027{ /*lint --e{715}*/
3028 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) );
3029
3030 return SCIP_OKAY;
3031}
3032
3033/**@} */
3034
3035/**@name Callback methods of event handler
3036 *
3037 * @{
3038 */
3039
3040static
3041SCIP_DECL_EVENTEXEC(eventExecBounddisjunction)
3042{ /*lint --e{715}*/
3043 assert(eventhdlr != NULL);
3044 assert(eventdata != NULL);
3045 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3046 assert(event != NULL);
3047
3048 /*SCIPdebugMsg(scip, "exec method of event handler for bound disjunction constraints\n");*/
3049
3050 assert(SCIPconsGetData((SCIP_CONS*)eventdata) != NULL);
3051 assert(SCIPconsIsActive((SCIP_CONS*)eventdata) || SCIPconsIsUpdatedeactivate((SCIP_CONS*)eventdata));
3052
3053 if( (SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDRELAXED) != 0 )
3054 {
3055 SCIP_CALL( SCIPenableCons(scip, (SCIP_CONS*)eventdata) );
3056 }
3057 else
3058 assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDTIGHTENED) != 0);
3059
3061
3062 return SCIP_OKAY;
3063}
3064
3065/**@} */
3066
3067/**@name Callback methods of conflict handler
3068 *
3069 * @{
3070 */
3071
3072/** conflict handler data struct */
3073struct SCIP_ConflicthdlrData
3074{
3075 SCIP_Real continuousfrac; /**< maximal percantage of continuous variables within a conflict */
3076};
3077
3078/** conflict processing method of conflict handler (called when conflict was found) */
3079static
3080SCIP_DECL_CONFLICTEXEC(conflictExecBounddisjunction)
3081{ /*lint --e{715}*/
3082 SCIP_VAR** vars;
3083 SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
3084 SCIP_BOUNDTYPE* boundtypes;
3085 SCIP_Real* bounds;
3086 SCIP_CONS* cons;
3087 char consname[SCIP_MAXSTRLEN];
3088 int nliterals;
3089 int ncontinuous;
3090 int i;
3091
3092 assert(conflicthdlr != NULL);
3093 assert(strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0);
3094 assert(bdchginfos != NULL || nbdchginfos == 0);
3095 assert(result != NULL);
3096
3097 /* don't process already resolved conflicts */
3098 if( resolved )
3099 {
3100 *result = SCIP_DIDNOTRUN;
3101 return SCIP_OKAY;
3102 }
3103
3104 conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
3105 assert(conflicthdlrdata != NULL);
3106
3107 *result = SCIP_DIDNOTFIND;
3108 ncontinuous = 0;
3109
3110 /* create array of variables, boundtypes, and bound values in conflict constraint */
3111 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbdchginfos) );
3112 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nbdchginfos) );
3113 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nbdchginfos) );
3114
3115 nliterals = 0;
3116
3117 for( i = 0; i < nbdchginfos; ++i )
3118 {
3119 SCIP_VAR* var;
3121 SCIP_BOUNDTYPE boundtype;
3122 int j;
3123
3124 assert(bdchginfos != NULL);
3125
3126 var = SCIPbdchginfoGetVar(bdchginfos[i]);
3127 assert(var != NULL);
3128
3129 boundtype = SCIPboundtypeOpposite(SCIPbdchginfoGetBoundtype(bdchginfos[i]));
3130 bound = relaxedbds[i];
3131
3132 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
3133 if( SCIPvarIsIntegral(var) )
3134 bound += (boundtype == SCIP_BOUNDTYPE_LOWER ? +1.0 : -1.0);
3135
3136 /* check whether we have seen the variable before */
3137 for( j = nliterals-1; j >= 0; --j )
3138 {
3139 if( vars[j] != var )
3140 continue;
3141
3142 /* check whether both literals contribute with the same bound type */
3143 if( boundtypes[j] == boundtype )
3144 {
3145 /* check whether the lower bound can be relaxed */
3146 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLT(scip, bound, bounds[j]) )
3147 {
3148 SCIPdebugMsg(scip, "relax lower bound of variable <%s> from %g to %g in bounddisjunction conflict\n",
3149 SCIPvarGetName(var), bounds[j], bound);
3150 bounds[j] = bound;
3151 }
3152 /* check whether the upper bound can be relaxed */
3153 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisGT(scip, bound, bounds[j]) )
3154 {
3155 SCIPdebugMsg(scip, "relax upper bound of variable <%s> from %g to %g in bounddisjunction conflict\n",
3156 SCIPvarGetName(var), bounds[j], bound);
3157 bounds[j] = bound;
3158 }
3159
3160 continue;
3161 }
3162 /* check whether the bounds are overlapping */
3163 else if( isOverlapping(scip, var, boundtype, bound, boundtypes[j], bounds[j]) )
3164 {
3165 /* the conflict is redundant -> discard the conflict constraint */
3166 SCIPdebugMsg(scip, "redundant bounddisjunction conflict due to overlapping\n");
3167 goto DISCARDCONFLICT;
3168 }
3169 }
3170
3171 vars[nliterals] = var;
3172 boundtypes[nliterals] = boundtype;
3173 bounds[nliterals] = bound;
3174
3175 /* check if the relaxed bound is really a relaxed bound */
3176 assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER || SCIPisGE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i])));
3177 assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_UPPER || SCIPisLE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i])));
3178
3179 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
3180 if( !SCIPvarIsIntegral(vars[nliterals]) )
3181 {
3182 if( (boundtypes[i] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), bounds[nliterals]))
3183 || (boundtypes[i] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), bounds[nliterals])) )
3184 {
3185 /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables)
3186 * -> discard the conflict constraint
3187 */
3188 SCIPdebugMsg(scip, "redundant bounddisjunction conflict due to globally fulfilled literal\n");
3189 goto DISCARDCONFLICT;
3190 }
3191 else
3192 ncontinuous++;
3193 }
3194
3195 nliterals++;
3196 }
3197
3198 /* create a constraint out of the conflict set */
3199 if( i == nbdchginfos && ncontinuous < conflicthdlrdata->continuousfrac * nbdchginfos + 0.5 )
3200 {
3202 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, consname, nliterals, vars, boundtypes, bounds,
3203 FALSE, FALSE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
3204
3205 /* add conflict to SCIP */
3206 SCIP_CALL( SCIPaddConflict(scip, node, cons, validnode, conftype, cutoffinvolved) );
3207 SCIPdebugMsg(scip, "added conflict\n");
3208 *result = SCIP_CONSADDED;
3209 }
3210
3211 DISCARDCONFLICT:
3212 /* free temporary memory */
3213 SCIPfreeBufferArray(scip, &bounds);
3214 SCIPfreeBufferArray(scip, &boundtypes);
3215 SCIPfreeBufferArray(scip, &vars);
3216
3217 return SCIP_OKAY;
3218}
3219
3220/** free method of conflict handler */
3221static
3222SCIP_DECL_CONFLICTFREE(conflictFreeBounddisjunction)
3223{
3224 SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
3225
3226 assert(conflicthdlr != NULL);
3227
3228 /* get conflict handler data */
3229 conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
3230 assert(conflicthdlrdata != NULL);
3231
3232 /* free conflict handler structure */
3233 SCIPfreeBlockMemory(scip, &conflicthdlrdata);
3234
3235 return SCIP_OKAY;
3236}
3237
3238/**@} */
3239
3240/** creates the handler for bound disjunction constraints and includes it in SCIP */
3242 SCIP* scip /**< SCIP data structure */
3243 )
3244{
3245 SCIP_CONSHDLRDATA* conshdlrdata;
3246 SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
3247 SCIP_CONFLICTHDLR* conflicthdlr;
3248 SCIP_CONSHDLR* conshdlr;
3249 SCIP_EVENTHDLR* eventhdlr;
3250
3251 /* create event handler for events on watched variables */
3253 eventExecBounddisjunction, NULL) );
3254
3255 /* allocate memory for conflict handler data */
3256 SCIP_CALL( SCIPallocBlockMemory(scip, &conflicthdlrdata) );
3257
3258 /* create conflict handler parameter */
3260 "conflict/" CONSHDLR_NAME "/continuousfrac", "maximal percantage of continuous variables within a conflict",
3261 &conflicthdlrdata->continuousfrac, FALSE, DEFAULT_CONTINUOUSFRAC, 0.0, 1.0, NULL, NULL) );
3262
3263 /* create conflict handler for bound disjunction constraints */
3265 conflictExecBounddisjunction, conflicthdlrdata) );
3266
3267 SCIP_CALL( SCIPsetConflicthdlrFree(scip, conflicthdlr, conflictFreeBounddisjunction) );
3268
3269 /* create constraint handler data */
3270 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
3271
3272 /* include constraint handler */
3275 consEnfolpBounddisjunction, consEnfopsBounddisjunction, consCheckBounddisjunction, consLockBounddisjunction,
3276 conshdlrdata) );
3277
3278 assert(conshdlr != NULL);
3279
3280 /* set non-fundamental callbacks via specific setter functions */
3281 SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveBounddisjunction) );
3282 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBounddisjunction, consCopyBounddisjunction) );
3283 SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveBounddisjunction) );
3284 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteBounddisjunction) );
3285 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreBounddisjunction) );
3286 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolBounddisjunction) );
3287 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBounddisjunction) );
3288 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsBounddisjunction) );
3289 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsBounddisjunction) );
3290 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseBounddisjunction) );
3291 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBounddisjunction, CONSHDLR_MAXPREROUNDS,
3293 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintBounddisjunction) );
3294 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropBounddisjunction, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3296 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropBounddisjunction) );
3297 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransBounddisjunction) );
3298 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBounddisjunction) );
3299 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphBounddisjunction) );
3300 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphBounddisjunction) );
3301
3302 return SCIP_OKAY;
3303}
3304
3305
3306/** creates and captures a bound disjunction constraint
3307 *
3308 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3309 */
3311 SCIP* scip, /**< SCIP data structure */
3312 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3313 const char* name, /**< name of constraint */
3314 int nvars, /**< number of variables in the constraint */
3315 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3316 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3317 SCIP_Real* bounds, /**< bounds of the literals */
3318 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3319 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3320 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3321 * Usually set to TRUE. */
3322 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3323 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3324 SCIP_Bool check, /**< should the constraint be checked for feasibility?
3325 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3326 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3327 * Usually set to TRUE. */
3328 SCIP_Bool local, /**< is constraint only valid locally?
3329 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3330 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3331 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3332 * adds coefficients to this constraint. */
3333 SCIP_Bool dynamic, /**< is constraint subject to aging?
3334 * Usually set to FALSE. Set to TRUE for own cuts which
3335 * are separated as constraints. */
3336 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3337 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3338 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3339 * if it may be moved to a more global node?
3340 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3341 )
3342{
3343 SCIP_CONSHDLR* conshdlr;
3344 SCIP_CONSDATA* consdata;
3345
3346 assert(scip != NULL);
3347
3348 /* find the bounddisjunction constraint handler */
3349 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3350 if( conshdlr == NULL )
3351 {
3352 SCIPerrorMessage("bound disjunction constraint handler not found\n");
3353 return SCIP_PLUGINNOTFOUND;
3354 }
3355
3356#ifndef NDEBUG
3357 {
3358 int v1;
3359 /* ensure that the given data neither contains overlapping nor redundant literals */
3360 for( v1 = 0; v1 < nvars; v1++ )
3361 {
3362 int v2;
3363 for( v2 = v1+1; v2 < nvars; v2++ )
3364 {
3365 assert(vars[v1] != vars[v2] || (SCIPboundtypeOpposite(boundtypes[v1]) == boundtypes[v2]
3366 && !isOverlapping(scip, vars[v1], boundtypes[v1], bounds[v1], boundtypes[v2], bounds[v2])));
3367 }
3368 }
3369 }
3370#endif
3371
3372 /* create the constraint specific data */
3373 SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars, boundtypes, bounds) );
3374
3375 /* create constraint */
3376 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3377 local, modifiable, dynamic, removable, stickingatnode) );
3378
3379 return SCIP_OKAY;
3380}
3381
3382/** creates and captures a bound disjunction constraint
3383 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
3384 * method SCIPcreateConsBounddisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
3385 *
3386 * @see SCIPcreateConsBounddisjunction() for information about the basic constraint flag configuration
3387 *
3388 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3389 */
3391 SCIP* scip, /**< SCIP data structure */
3392 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3393 const char* name, /**< name of constraint */
3394 int nvars, /**< number of variables in the constraint */
3395 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3396 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3397 SCIP_Real* bounds /**< bounds of the literals */
3398 )
3399{
3400 assert(scip != NULL);
3401
3402 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds,
3404
3405 return SCIP_OKAY;
3406}
3407
3408/** creates and captures a bound disjunction constraint with possibly redundant literals
3409 *
3410 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3411 */
3413 SCIP* scip, /**< SCIP data structure */
3414 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3415 const char* name, /**< name of constraint */
3416 int nvars, /**< number of variables in the constraint */
3417 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3418 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3419 SCIP_Real* bounds, /**< bounds of the literals */
3420 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3421 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3422 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3423 * Usually set to TRUE. */
3424 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3425 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3426 SCIP_Bool check, /**< should the constraint be checked for feasibility?
3427 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3428 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3429 * Usually set to TRUE. */
3430 SCIP_Bool local, /**< is constraint only valid locally?
3431 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3432 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3433 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3434 * adds coefficients to this constraint. */
3435 SCIP_Bool dynamic, /**< is constraint subject to aging?
3436 * Usually set to FALSE. Set to TRUE for own cuts which
3437 * are separated as constraints. */
3438 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3439 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3440 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3441 * if it may be moved to a more global node?
3442 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3443 )
3444{
3445 SCIP_CONSHDLR* conshdlr;
3446 SCIP_CONSDATA* consdata;
3447
3448 assert(scip != NULL);
3449
3450 /* find the bounddisjunction constraint handler */
3451 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3452 if( conshdlr == NULL )
3453 {
3454 SCIPerrorMessage("bound disjunction constraint handler not found\n");
3455 return SCIP_PLUGINNOTFOUND;
3456 }
3457
3458 /* create the constraint specific data */
3459 SCIP_CALL( consdataCreateRedundant(scip, &consdata, nvars, vars, boundtypes, bounds) );
3460
3461 /* create constraint */
3462 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3463 local, modifiable, dynamic, removable, stickingatnode) );
3464
3465 return SCIP_OKAY;
3466}
3467
3468/** creates and captures a bound disjunction constraint with possibly redundant literals
3469 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
3470 * method SCIPcreateConsBounddisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
3471 *
3472 * @see SCIPcreateConsBounddisjunction() for information about the basic constraint flag configuration
3473 *
3474 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3475 */
3477 SCIP* scip, /**< SCIP data structure */
3478 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3479 const char* name, /**< name of constraint */
3480 int nvars, /**< number of variables in the constraint */
3481 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3482 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3483 SCIP_Real* bounds /**< bounds of the literals */
3484 )
3485{
3486 assert(scip != NULL);
3487
3488 SCIP_CALL( SCIPcreateConsBounddisjunctionRedundant(scip, cons, name, nvars, vars, boundtypes, bounds,
3490
3491 return SCIP_OKAY;
3492}
3493
3494/** gets number of variables in bound disjunction constraint */ /*lint -e{715}*/
3496 SCIP* scip, /**< SCIP data structure */
3497 SCIP_CONS* cons /**< constraint data */
3498 )
3499{
3500 SCIP_CONSDATA* consdata;
3501
3502 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3503 {
3504 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3505 SCIPABORT();
3506 return 0; /*lint !e527*/
3507 }
3508
3509 consdata = SCIPconsGetData(cons);
3510 assert(consdata != NULL);
3511
3512 return consdata->nvars;
3513}
3514
3515/** gets array of variables in bound disjunction constraint */ /*lint -e{715}*/
3517 SCIP* scip, /**< SCIP data structure */
3518 SCIP_CONS* cons /**< constraint data */
3519 )
3520{
3521 SCIP_CONSDATA* consdata;
3522
3523 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3524 {
3525 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3526 SCIPABORT();
3527 return NULL; /*lint !e527*/
3528 }
3529
3530 consdata = SCIPconsGetData(cons);
3531 assert(consdata != NULL);
3532
3533 return consdata->vars;
3534}
3535
3536/** gets array of bound types in bound disjunction constraint */ /*lint -e{715}*/
3538 SCIP* scip, /**< SCIP data structure */
3539 SCIP_CONS* cons /**< constraint data */
3540 )
3541{
3542 SCIP_CONSDATA* consdata;
3543
3544 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3545 {
3546 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3547 SCIPABORT();
3548 return NULL; /*lint !e527*/
3549 }
3550
3551 consdata = SCIPconsGetData(cons);
3552 assert(consdata != NULL);
3553
3554 return consdata->boundtypes;
3555}
3556
3557/** gets array of bounds in bound disjunction constraint */ /*lint -e{715}*/
3559 SCIP* scip, /**< SCIP data structure */
3560 SCIP_CONS* cons /**< constraint data */
3561 )
3562{
3563 SCIP_CONSDATA* consdata;
3564
3565 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3566 {
3567 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3568 SCIPABORT();
3569 return NULL; /*lint !e527*/
3570 }
3571
3572 consdata = SCIPconsGetData(cons);
3573 assert(consdata != NULL);
3574
3575 return consdata->bounds;
3576}
static long bound
SCIP_VAR * a
Definition: circlepacking.c:66
SCIP_VAR ** b
Definition: circlepacking.c:65
#define isFeasGE(scip, var, val1, val2)
static SCIP_RETCODE applyGlobalBounds(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *redundant)
static SCIP_Bool isConsViolated(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds)
static SCIP_DECL_CONSCOPY(consCopyBounddisjunction)
#define AGEINCREASE(n)
#define CONSHDLR_NEEDSCONS
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphBounddisjunction)
#define CONFLICTHDLR_PRIORITY
#define isFeasLT(scip, var, val1, val2)
#define CONFLICTHDLR_NAME
static SCIP_RETCODE removeFixedVariables(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *redundant)
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
#define CONSHDLR_CHECKPRIORITY
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphBounddisjunction)
#define CONSHDLR_DESC
static SCIP_DECL_CONSDEACTIVE(consDeactiveBounddisjunction)
static SCIP_DECL_CONSLOCK(consLockBounddisjunction)
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *ndelconss, int *naddconss)
static SCIP_DECL_CONSGETVARS(consGetVarsBounddisjunction)
#define CONSHDLR_PROP_TIMING
static SCIP_DECL_EVENTEXEC(eventExecBounddisjunction)
#define CONFLICTHDLR_DESC
static SCIP_DECL_CONSENFOPS(consEnfopsBounddisjunction)
static SCIP_DECL_CONSRESPROP(consRespropBounddisjunction)
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
static SCIP_DECL_CONFLICTEXEC(conflictExecBounddisjunction)
static SCIP_RETCODE enforceCurrentSol(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *reduceddom, SCIP_Bool *registeredbrcand)
#define CONSHDLR_MAXPREROUNDS
#define isFeasLE(scip, var, val1, val2)
static SCIP_DECL_CONSPROP(consPropBounddisjunction)
static SCIP_DECL_CONSEXITPRE(consExitpreBounddisjunction)
static SCIP_DECL_CONSCHECK(consCheckBounddisjunction)
static SCIP_DECL_CONSPARSE(consParseBounddisjunction)
static void consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file, SCIP_Bool endline)
#define DEFAULT_CONTINUOUSFRAC
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
static SCIP_Bool isLiteralViolated(SCIP *scip, SCIP_CONSDATA *consdata, int pos)
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, int pos)
static SCIP_DECL_CONSENFOLP(consEnfolpBounddisjunction)
static SCIP_RETCODE switchWatchedvars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
static SCIP_RETCODE dropEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int filterpos)
#define isFeasGT(scip, var, val1, val2)
static SCIP_Bool isLiteralSatisfied(SCIP *scip, SCIP_CONSDATA *consdata, int pos)
static void consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
static SCIP_DECL_CONSINITSOL(consInitsolBounddisjunction)
static SCIP_RETCODE consdataCreateRedundant(SCIP *scip, SCIP_CONSDATA **consdata, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds)
#define CONSHDLR_PROPFREQ
static SCIP_DECL_CONSTRANS(consTransBounddisjunction)
static SCIP_DECL_CONSFREE(consFreeBounddisjunction)
static SCIP_RETCODE createNAryBranch(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
static SCIP_DECL_CONSPRESOL(consPresolBounddisjunction)
#define CONSHDLR_PRESOLTIMING
static SCIP_DECL_CONSDELETE(consDeleteBounddisjunction)
static SCIP_RETCODE catchEvents(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int *filterpos)
#define CONSHDLR_EAGERFREQ
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, int pos)
static SCIP_DECL_CONSPRINT(consPrintBounddisjunction)
#define EVENTHDLR_DESC
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
static SCIP_RETCODE registerBranchingCandidates(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *cutoff, SCIP_Bool *neednarybranch)
#define CONSHDLR_ENFOPRIORITY
static SCIP_DECL_CONSENFORELAX(consEnforelaxBounddisjunction)
static SCIP_RETCODE processWatchedVars(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, SCIP_Bool *infeasible, SCIP_Bool *reduceddom, SCIP_Bool *mustcheck)
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_RESULT *result)
#define CONSHDLR_NAME
static SCIP_DECL_CONFLICTFREE(conflictFreeBounddisjunction)
#define EVENTHDLR_NAME
static SCIP_RETCODE disableCons(SCIP *scip, SCIP_CONS *cons)
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_Real bound, SCIP_Bool *redundant)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBounddisjunction)
static SCIP_DECL_CONSGETNVARS(consGetNVarsBounddisjunction)
#define CONSHDLR_DELAYPROP
static SCIP_DECL_CONSACTIVE(consActiveBounddisjunction)
static SCIP_Bool isOverlapping(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype1, SCIP_Real bound1, SCIP_BOUNDTYPE boundtype2, SCIP_Real bound2)
constraint handler for bound disjunction constraints
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
Constraint handler for the set partitioning / packing / covering constraints .
#define NULL
Definition: def.h:266
#define SCIP_MAXSTRLEN
Definition: def.h:287
#define SCIP_Longint
Definition: def.h:157
#define SCIP_REAL_MAX
Definition: def.h:173
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:172
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_LONGINT_FORMAT
Definition: def.h:164
#define SCIPABORT()
Definition: def.h:345
#define REALABS(x)
Definition: def.h:196
#define SCIP_LONGINT_MAX
Definition: def.h:158
#define SCIP_CALL(x)
Definition: def.h:373
power and signed power expression handlers
variable expression handler
SCIP_Real * SCIPgetBoundsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBasicBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds)
SCIP_RETCODE SCIPcreateConsBounddisjunction(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, 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)
int SCIPgetNVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsBounddisjunctionRedundant(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds, 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_BOUNDTYPE * SCIPgetBoundtypesBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsSetpack(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)
Definition: cons_setppc.c:9426
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 SCIPcreateConsLogicor(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 SCIPcreateConsBasicBounddisjunctionRedundant(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_BOUNDTYPE *boundtypes, SCIP_Real *bounds)
SCIP_VAR ** SCIPgetVarsBounddisjunction(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPincludeConshdlrBounddisjunction(SCIP *scip)
SCIP_Bool SCIPisConsCompressionEnabled(SCIP *scip)
Definition: scip_copy.c:660
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_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_var.c:390
SCIP_RETCODE SCIPcreateExprPow(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_Real exponent, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_pow.c:3193
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:606
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:734
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:390
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
SCIP_RETCODE SCIPdelConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons)
Definition: scip_prob.c:3425
SCIP_RETCODE SCIPaddConsNode(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode)
Definition: scip_prob.c:3324
SCIP_RETCODE SCIPaddConflict(SCIP *scip, SCIP_NODE *node, SCIP_CONS *cons, SCIP_NODE *validnode, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_prob.c:3229
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip_message.c:225
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_Real SCIPrelDiff(SCIP_Real val1, SCIP_Real val2)
Definition: misc.c:11215
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
void SCIPswapInts(int *value1, int *value2)
Definition: misc.c:10373
SCIP_Real SCIPcalcNodeselPriority(SCIP *scip, SCIP_VAR *var, SCIP_BRANCHDIR branchdir, SCIP_Real targetvalue)
Definition: scip_branch.c:927
SCIP_RETCODE SCIPaddExternBranchCand(SCIP *scip, SCIP_VAR *var, SCIP_Real score, SCIP_Real solval)
Definition: scip_branch.c:672
SCIP_Real SCIPcalcChildEstimate(SCIP *scip, SCIP_VAR *var, SCIP_Real targetvalue)
Definition: scip_branch.c:954
SCIP_RETCODE SCIPcreateChild(SCIP *scip, SCIP_NODE **node, SCIP_Real nodeselprio, SCIP_Real estimate)
Definition: scip_branch.c:1024
SCIP_BOUNDTYPE SCIPboundtypeOpposite(SCIP_BOUNDTYPE boundtype)
Definition: lp.c:17231
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_CONFLICTHDLRDATA * SCIPconflicthdlrGetData(SCIP_CONFLICTHDLR *conflicthdlr)
const char * SCIPconflicthdlrGetName(SCIP_CONFLICTHDLR *conflicthdlr)
SCIP_RETCODE SCIPaddConflictBd(SCIP *scip, SCIP_VAR *var, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPincludeConflicthdlrBasic(SCIP *scip, SCIP_CONFLICTHDLR **conflicthdlrptr, const char *name, const char *desc, int priority, SCIP_DECL_CONFLICTEXEC((*conflictexec)), SCIP_CONFLICTHDLRDATA *conflicthdlrdata)
SCIP_RETCODE SCIPsetConflicthdlrFree(SCIP *scip, SCIP_CONFLICTHDLR *conflicthdlr, SCIP_DECL_CONFLICTFREE((*conflictfree)))
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4227
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:693
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETPERMSYMGRAPH((*consgetpermsymgraph)))
Definition: scip_cons.c:900
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip_cons.c:516
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH((*consgetsignedpermsymgraph)))
Definition: scip_cons.c:924
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8244
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_RETCODE SCIPenableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1838
SCIP_Bool SCIPconsIsPropagationEnabled(SCIP_CONS *cons)
Definition: cons.c:8332
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8383
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2537
SCIP_RETCODE SCIPenableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1952
int SCIPconsGetValidDepth(SCIP_CONS *cons)
Definition: cons.c:8297
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8343
SCIP_Bool SCIPconsIsUpdatedeactivate(SCIP_CONS *cons)
Definition: cons.c:8285
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8523
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:998
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8453
SCIP_RETCODE SCIPdisableCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1872
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1813
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8463
SCIP_Bool SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8643
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8493
SCIP_RETCODE SCIPdisableConsPropagation(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1982
SCIP_RETCODE SCIPaddConsAge(SCIP *scip, SCIP_CONS *cons, SCIP_Real deltaage)
Definition: scip_cons.c:1756
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8483
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:111
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:361
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:407
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1424
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#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 SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition: scip_nlp.c:396
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:110
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
Definition: scip_nlp.c:1058
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:954
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:125
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1213
int SCIPgetNRuns(SCIP *scip)
SCIP_Longint SCIPgetNConflictConssApplied(SCIP *scip)
SCIP_Bool SCIPisFeasGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPparseReal(SCIP *scip, const char *str, SCIP_Real *value, char **endptr)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:672
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5326
SCIP_RETCODE SCIPvarGetProbvarBound(SCIP_VAR **var, SCIP_Real *bound, SCIP_BOUNDTYPE *boundtype)
Definition: var.c:12496
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4474
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17775
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17626
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:17565
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18171
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17588
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:5738
SCIP_RETCODE SCIPchgVarUbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:5013
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12245
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5443
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:17611
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18115
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4382
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4560
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:17446
SCIP_VAR * SCIPbdchginfoGetVar(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18707
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17637
SCIP_Real SCIPcomputeVarLbGlobal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6586
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18161
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6628
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18105
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:5624
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_RETCODE SCIPchgVarLbNode(SCIP *scip, SCIP_NODE *node, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_var.c:4969
SCIP_Longint SCIPvarGetNBranchingsCurrentRun(SCIP_VAR *var, SCIP_BRANCHDIR dir)
Definition: var.c:15771
SCIP_Real SCIPcomputeVarUbGlobal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6607
SCIP_BOUNDTYPE SCIPbdchginfoGetBoundtype(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18727
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:6649
SCIP_Real SCIPbdchginfoGetNewbound(SCIP_BDCHGINFO *bdchginfo)
Definition: var.c:18697
void SCIPsortPtrRealInt(void **ptrarray, SCIP_Real *realarray, int *intarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10880
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10869
SCIP_RETCODE SCIPaddSymgraphEdge(SCIP *scip, SYM_GRAPH *graph, int first, int second, SCIP_Bool hasval, SCIP_Real val)
SCIP_RETCODE SCIPaddSymgraphOpnode(SCIP *scip, SYM_GRAPH *graph, int op, int *nodeidx)
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPaddSymgraphValnode(SCIP *scip, SYM_GRAPH *graph, SCIP_Real val, int *nodeidx)
SCIP_RETCODE SCIPaddSymgraphConsnode(SCIP *scip, SYM_GRAPH *graph, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, int *nodeidx)
SCIP_RETCODE SCIPaddSymgraphVarAggregation(SCIP *scip, SYM_GRAPH *graph, int rootidx, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real constant)
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
public methods for conflict analysis handlers
public methods for managing constraints
public methods for managing events
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
public methods for problem variables
public methods for branching rule plugins and branching
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 event handler plugins and event handlers
public functions to work with algebraic expressions
general public methods
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 querying solving statistics
public methods for the branch-and-bound tree
public methods for SCIP variables
structs for symmetry computations
methods for dealing with symmetry detection graphs
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
struct SCIP_ConflicthdlrData SCIP_CONFLICTHDLRDATA
Definition: type_conflict.h:50
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:79
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:78
#define SCIP_EVENTTYPE_BOUNDRELAXED
Definition: type_event.h:124
#define SCIP_EVENTTYPE_BOUNDTIGHTENED
Definition: type_event.h:123
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:77
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:80
@ SCIP_EXPRCURV_CONVEX
Definition: type_expr.h:63
@ SCIP_BRANCHDIR_DOWNWARDS
Definition: type_history.h:43
@ SCIP_BRANCHDIR_UPWARDS
Definition: type_history.h:44
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
@ SCIP_VERBLEVEL_MINIMAL
Definition: type_message.h:54
@ 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_CONSADDED
Definition: type_result.h:52
@ SCIP_BRANCHED
Definition: type_result.h:54
@ 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_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
@ SCIP_STAGE_TRANSFORMING
Definition: type_set.h:46
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
@ SYM_CONSOPTYPE_BDDISJ
Definition: type_symmetry.h:80
@ SYM_CONSOPTYPE_SUM
Definition: type_symmetry.h:83
@ SYM_SYMTYPE_SIGNPERM
Definition: type_symmetry.h:62
@ SYM_SYMTYPE_PERM
Definition: type_symmetry.h:61
@ SCIP_VARTYPE_CONTINUOUS
Definition: type_var.h:71
@ SCIP_VARSTATUS_FIXED
Definition: type_var.h:52
@ SCIP_VARSTATUS_MULTAGGR
Definition: type_var.h:54