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