Scippy

SCIP

Solving Constraint Integer Programs

cons_or.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2025 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file cons_or.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief Constraint handler for "or" constraints, \f$r = x_1 \vee x_2 \vee \dots \vee x_n\f$
28 * @author Tobias Achterberg
29 * @author Stefan Heinz
30 * @author Michael Winkler
31 *
32 * This constraint handler deals with "or" constraint. These are constraint of the form:
33 *
34 * \f[
35 * r = x_1 \vee x_2 \vee \dots \vee x_n
36 * \f]
37 *
38 * where \f$x_i\f$ is a binary variable for all \f$i\f$. Hence, \f$r\f$ is also of binary type. The variable \f$r\f$ is
39 * called resultant and the \f$x\f$'s operators.
40 */
41
42/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
43
45#include "scip/cons_and.h"
46#include "scip/cons_or.h"
47#include "scip/pub_cons.h"
48#include "scip/pub_event.h"
49#include "scip/pub_lp.h"
50#include "scip/pub_message.h"
51#include "scip/pub_misc.h"
52#include "scip/pub_var.h"
53#include "scip/scip_conflict.h"
54#include "scip/scip_cons.h"
55#include "scip/scip_copy.h"
56#include "scip/scip_cut.h"
57#include "scip/scip_event.h"
58#include "scip/scip_general.h"
59#include "scip/scip_lp.h"
60#include "scip/scip_mem.h"
61#include "scip/scip_message.h"
62#include "scip/scip_numerics.h"
63#include "scip/scip_prob.h"
64#include "scip/scip_probing.h"
65#include "scip/scip_sol.h"
66#include "scip/scip_tree.h"
67#include "scip/scip_var.h"
68#include "scip/symmetry_graph.h"
70#include <string.h>
71
72
73/* constraint handler properties */
74#define CONSHDLR_NAME "or"
75#define CONSHDLR_DESC "constraint handler for or constraints: r = or(x1, ..., xn)"
76#define CONSHDLR_SEPAPRIORITY +850000 /**< priority of the constraint handler for separation */
77#define CONSHDLR_ENFOPRIORITY -850000 /**< priority of the constraint handler for constraint enforcing */
78#define CONSHDLR_CHECKPRIORITY -850000 /**< priority of the constraint handler for checking feasibility */
79#define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
80#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
81#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
82 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
83#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
84#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
85#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
86#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
87
88#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
89#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
90
91#define EVENTHDLR_NAME "or"
92#define EVENTHDLR_DESC "event handler for or constraints"
93
94
95/*
96 * Data structures
97 */
98
99/** constraint data for or constraints */
100struct SCIP_ConsData
101{
102 SCIP_VAR** vars; /**< variables in the or operation */
103 SCIP_VAR* resvar; /**< resultant variable */
104 SCIP_ROW** rows; /**< rows for linear relaxation of or constraint */
105 int nvars; /**< number of variables in or operation */
106 int varssize; /**< size of vars array */
107 int rowssize; /**< size of rows array */
108 int watchedvar1; /**< position of first watched operator variable */
109 int watchedvar2; /**< position of second watched operator variable */
110 int filterpos1; /**< event filter position of first watched operator variable */
111 int filterpos2; /**< event filter position of second watched operator variable */
112 unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
113 unsigned int nofixedone:1; /**< is none of the operator variables fixed to TRUE? */
114 unsigned int impladded:1; /**< were the implications of the constraint already added? */
115 unsigned int opimpladded:1; /**< was the implication for 2 operands with fixed resultant added? */
116};
117
118/** constraint handler data */
119struct SCIP_ConshdlrData
120{
121 SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
122};
123
124
125/*
126 * Propagation rules
127 */
128
130{
131 PROPRULE_1 = 0, /**< v_i = TRUE => r = TRUE */
132 PROPRULE_2 = 1, /**< r = FALSE => v_i = FALSE for all i */
133 PROPRULE_3 = 2, /**< v_i = FALSE for all i => r = FALSE */
134 PROPRULE_4 = 3, /**< r = TRUE, v_i = FALSE for all i except j => v_j = TRUE */
135 PROPRULE_INVALID = 4 /**< propagation was applied without a specific propagation rule */
137typedef enum Proprule PROPRULE;
138
139
140/*
141 * Local methods
142 */
143
144/** installs rounding locks for the given variable in the given or constraint */
145static
147 SCIP* scip, /**< SCIP data structure */
148 SCIP_CONS* cons, /**< or constraint */
149 SCIP_VAR* var /**< variable of constraint entry */
150 )
151{
153
154 /* rounding in both directions may violate the constraint */
155 SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
156
157 return SCIP_OKAY;
158}
159
160/** removes rounding locks for the given variable in the given or constraint */
161static
163 SCIP* scip, /**< SCIP data structure */
164 SCIP_CONS* cons, /**< or constraint */
165 SCIP_VAR* var /**< variable of constraint entry */
166 )
167{
169
170 /* rounding in both directions may violate the constraint */
171 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
172
173 return SCIP_OKAY;
174}
175
176/** creates constraint handler data */
177static
179 SCIP* scip, /**< SCIP data structure */
180 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
181 SCIP_EVENTHDLR* eventhdlr /**< event handler */
182 )
183{
184 assert(scip != NULL);
185 assert(conshdlrdata != NULL);
186 assert(eventhdlr != NULL);
187
188 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
189
190 /* set event handler for catching events on watched variables */
191 (*conshdlrdata)->eventhdlr = eventhdlr;
192
193 return SCIP_OKAY;
194}
195
196/** frees constraint handler data */
197static
199 SCIP* scip, /**< SCIP data structure */
200 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
201 )
202{
203 assert(conshdlrdata != NULL);
204 assert(*conshdlrdata != NULL);
205
206 SCIPfreeBlockMemory(scip, conshdlrdata);
207}
208
209/** gets number of LP rows needed for the LP relaxation of the constraint */
210static
212 SCIP_CONSDATA* consdata /**< constraint data */
213 )
214{
215 assert(consdata != NULL);
216
217 return consdata->nvars + 1;
218}
219
220/** catches events for the watched variable at given position */
221static
223 SCIP* scip, /**< SCIP data structure */
224 SCIP_CONSDATA* consdata, /**< or constraint data */
225 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
226 int pos, /**< array position of variable to catch bound change events for */
227 int* filterpos /**< pointer to store position of event filter entry */
228 )
229{
230 assert(consdata != NULL);
231 assert(consdata->vars != NULL);
232 assert(eventhdlr != NULL);
233 assert(0 <= pos && pos < consdata->nvars);
234 assert(filterpos != NULL);
235
236 /* catch tightening events for upper bound and relaxed events for lower bounds on watched variable */
238 eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
239
240 return SCIP_OKAY;
241}
242
243
244/** drops events for the watched variable at given position */
245static
247 SCIP* scip, /**< SCIP data structure */
248 SCIP_CONSDATA* consdata, /**< or constraint data */
249 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
250 int pos, /**< array position of watched variable to drop bound change events for */
251 int filterpos /**< position of event filter entry */
252 )
253{
254 assert(consdata != NULL);
255 assert(consdata->vars != NULL);
256 assert(eventhdlr != NULL);
257 assert(0 <= pos && pos < consdata->nvars);
258 assert(filterpos >= 0);
259
260 /* drop tightening events for upper bound and relaxed events for lower bounds on watched variable */
262 eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
263
264 return SCIP_OKAY;
265}
266
267/** catches needed events on all variables of constraint, except the special ones for watched variables */
268static
270 SCIP* scip, /**< SCIP data structure */
271 SCIP_CONSDATA* consdata, /**< or constraint data */
272 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
273 )
274{
275 int i;
276
277 assert(consdata != NULL);
278
279 /* catch bound change events for both bounds on resultant variable */
281 eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
282
283 /* catch tightening events for lower bound and relaxed events for upper bounds on operator variables */
284 for( i = 0; i < consdata->nvars; ++i )
285 {
287 eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
288 }
289
290 return SCIP_OKAY;
291}
292
293/** drops events on all variables of constraint, except the special ones for watched variables */
294static
296 SCIP* scip, /**< SCIP data structure */
297 SCIP_CONSDATA* consdata, /**< or constraint data */
298 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
299 )
300{
301 int i;
302
303 assert(consdata != NULL);
304
305 /* drop bound change events for both bounds on resultant variable */
307 eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
308
309 /* drop tightening events for lower bound and relaxed events for upper bounds on operator variables */
310 for( i = 0; i < consdata->nvars; ++i )
311 {
313 eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
314 }
315
316 return SCIP_OKAY;
317}
318
319/** stores the given variable numbers as watched variables, and updates the event processing */
320static
322 SCIP* scip, /**< SCIP data structure */
323 SCIP_CONSDATA* consdata, /**< or constraint data */
324 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
325 int watchedvar1, /**< new first watched variable */
326 int watchedvar2 /**< new second watched variable */
327 )
328{
329 assert(consdata != NULL);
330 assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
331 assert(watchedvar1 != -1 || watchedvar2 == -1);
332 assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
333 assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
334
335 /* if one watched variable is equal to the old other watched variable, just switch positions */
336 if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
337 {
338 int tmp;
339
340 tmp = consdata->watchedvar1;
341 consdata->watchedvar1 = consdata->watchedvar2;
342 consdata->watchedvar2 = tmp;
343 tmp = consdata->filterpos1;
344 consdata->filterpos1 = consdata->filterpos2;
345 consdata->filterpos2 = tmp;
346 }
347 assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
348 assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
349
350 /* drop events on old watched variables */
351 if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
352 {
353 assert(consdata->filterpos1 != -1);
354 SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
355 }
356 if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
357 {
358 assert(consdata->filterpos2 != -1);
359 SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
360 }
361
362 /* catch events on new watched variables */
363 if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
364 {
365 SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) );
366 }
367 if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
368 {
369 SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) );
370 }
371
372 /* set the new watched variables */
373 consdata->watchedvar1 = watchedvar1;
374 consdata->watchedvar2 = watchedvar2;
375
376 return SCIP_OKAY;
377}
378
379/** ensures, that the vars array can store at least num entries */
380static
382 SCIP* scip, /**< SCIP data structure */
383 SCIP_CONSDATA* consdata, /**< linear constraint data */
384 int num /**< minimum number of entries to store */
385 )
386{
387 assert(consdata != NULL);
388 assert(consdata->nvars <= consdata->varssize);
389
390 if( num > consdata->varssize )
391 {
392 int newsize;
393
394 newsize = SCIPcalcMemGrowSize(scip, num);
395 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
396 consdata->varssize = newsize;
397 }
398 assert(num <= consdata->varssize);
399
400 return SCIP_OKAY;
401}
402
403/** creates constraint data for or constraint */
404static
406 SCIP* scip, /**< SCIP data structure */
407 SCIP_CONSDATA** consdata, /**< pointer to store the constraint data */
408 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
409 int nvars, /**< number of variables in the or operation */
410 SCIP_VAR** vars, /**< variables in or operation */
411 SCIP_VAR* resvar /**< resultant variable */
412 )
413{
414 assert(consdata != NULL);
415 assert(nvars == 0 || vars != NULL);
416 assert(resvar != NULL);
417
418 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
419 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
420 (*consdata)->resvar = resvar;
421 (*consdata)->rows = NULL;
422 (*consdata)->nvars = nvars;
423 (*consdata)->varssize = nvars;
424 (*consdata)->rowssize = 0;
425 (*consdata)->watchedvar1 = -1;
426 (*consdata)->watchedvar2 = -1;
427 (*consdata)->filterpos1 = -1;
428 (*consdata)->filterpos2 = -1;
429 (*consdata)->propagated = FALSE;
430 (*consdata)->nofixedone = FALSE;
431 (*consdata)->impladded = FALSE;
432 (*consdata)->opimpladded = FALSE;
433
434 /* get transformed variables, if we are in the transformed problem */
436 {
437 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
438 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->resvar, &(*consdata)->resvar) );
439
440 /* catch needed events on variables */
441 SCIP_CALL( consdataCatchEvents(scip, *consdata, eventhdlr) );
442 }
443
444 return SCIP_OKAY;
445}
446
447/** releases LP rows of constraint data and frees rows array */
448static
450 SCIP* scip, /**< SCIP data structure */
451 SCIP_CONSDATA* consdata /**< constraint data */
452 )
453{
454 int r;
455
456 assert(consdata != NULL);
457
458 if( consdata->rows != NULL )
459 {
460 int nrows;
461
462 nrows = consdataGetNRows(consdata);
463
464 for( r = 0; r < nrows; ++r )
465 {
466 SCIP_CALL( SCIPreleaseRow(scip, &consdata->rows[r]) );
467 }
468 SCIPfreeBlockMemoryArray(scip, &consdata->rows, consdata->rowssize);
469 }
470
471 return SCIP_OKAY;
472}
473
474/** frees constraint data for or constraint */
475static
477 SCIP* scip, /**< SCIP data structure */
478 SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
479 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
480 )
481{
482 assert(consdata != NULL);
483 assert(*consdata != NULL);
484
486 {
487 /* drop events for watched variables */
488 SCIP_CALL( consdataSwitchWatchedvars(scip, *consdata, eventhdlr, -1, -1) );
489
490 /* drop all other events on variables */
491 SCIP_CALL( consdataDropEvents(scip, *consdata, eventhdlr) );
492 }
493 else
494 {
495 assert((*consdata)->watchedvar1 == -1);
496 assert((*consdata)->watchedvar2 == -1);
497 }
498
499 /* release and free the rows */
500 SCIP_CALL( consdataFreeRows(scip, *consdata) );
501
502 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
503 SCIPfreeBlockMemory(scip, consdata);
504
505 return SCIP_OKAY;
506}
507
508/** prints or constraint to file stream */
509static
511 SCIP* scip, /**< SCIP data structure */
512 SCIP_CONSDATA* consdata, /**< or constraint data */
513 FILE* file /**< output file (or NULL for standard output) */
514 )
515{
516 assert(consdata != NULL);
517
518 /* print resultant */
519 SCIP_CALL( SCIPwriteVarName(scip, file, consdata->resvar, TRUE) );
520
521 /* start the variable list */
522 SCIPinfoMessage(scip, file, " == or(");
523
524 /* print variable list */
525 SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
526
527 /* close the variable list */
528 SCIPinfoMessage(scip, file, ")");
529
530 return SCIP_OKAY;
531}
532
533/** adds coefficient in or constraint */
534static
536 SCIP* scip, /**< SCIP data structure */
537 SCIP_CONS* cons, /**< linear constraint */
538 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
539 SCIP_VAR* var /**< variable to add to the constraint */
540 )
541{
542 SCIP_CONSDATA* consdata;
543 SCIP_Bool transformed;
544
545 assert(var != NULL);
546
547 consdata = SCIPconsGetData(cons);
548 assert(consdata != NULL);
549 assert(consdata->rows == NULL);
550
551 /* are we in the transformed problem? */
552 transformed = SCIPconsIsTransformed(cons);
553
554 /* always use transformed variables in transformed constraints */
555 if( transformed )
556 {
557 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
558 }
559 assert(var != NULL);
560 assert(transformed == SCIPvarIsTransformed(var));
561
562 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
563 consdata->vars[consdata->nvars] = var;
564 consdata->nvars++;
565
566 /* if we are in transformed problem, catch the variable's events */
567 if( transformed )
568 {
569 /* catch bound change events of variable */
571 eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
572 }
573
574 /* install the rounding locks for the new variable */
575 SCIP_CALL( lockRounding(scip, cons, var) );
576
577 /**@todo update LP rows */
578 if( consdata->rows != NULL )
579 {
580 SCIPerrorMessage("cannot add coefficients to or constraint after LP relaxation was created\n");
581 return SCIP_INVALIDCALL;
582 }
583
584 return SCIP_OKAY;
585}
586
587/** deletes coefficient at given position from or constraint data */
588static
590 SCIP* scip, /**< SCIP data structure */
591 SCIP_CONS* cons, /**< or constraint */
592 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
593 int pos /**< position of coefficient to delete */
594 )
595{
596 SCIP_CONSDATA* consdata;
597
598 assert(eventhdlr != NULL);
599
600 consdata = SCIPconsGetData(cons);
601 assert(consdata != NULL);
602 assert(0 <= pos && pos < consdata->nvars);
603 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
604
605 /* remove the rounding locks of the variable */
606 SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
607
608 if( SCIPconsIsTransformed(cons) )
609 {
610 /* drop bound change events of variable */
612 eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
613 }
614
615 if( SCIPconsIsTransformed(cons) )
616 {
617 /* if the position is watched, stop watching the position */
618 if( consdata->watchedvar1 == pos )
619 {
620 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar2, -1) );
621 }
622 if( consdata->watchedvar2 == pos )
623 {
624 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar1, -1) );
625 }
626 }
627 assert(pos != consdata->watchedvar1);
628 assert(pos != consdata->watchedvar2);
629
630 /* move the last variable to the free slot */
631 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
632 consdata->nvars--;
633
634 /* if the last variable (that moved) was watched, update the watched position */
635 if( consdata->watchedvar1 == consdata->nvars )
636 consdata->watchedvar1 = pos;
637 if( consdata->watchedvar2 == consdata->nvars )
638 consdata->watchedvar2 = pos;
639
640 consdata->propagated = FALSE;
641
642 return SCIP_OKAY;
643}
644
645/** deletes all zero-fixed variables */
646static
648 SCIP* scip, /**< SCIP data structure */
649 SCIP_CONS* cons, /**< or constraint */
650 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
651 )
652{
653 SCIP_CONSDATA* consdata;
654 SCIP_VAR* var;
655 int v;
656
657 consdata = SCIPconsGetData(cons);
658 assert(consdata != NULL);
659 assert(consdata->nvars == 0 || consdata->vars != NULL);
660
661 v = 0;
662 while( v < consdata->nvars )
663 {
664 var = consdata->vars[v];
665 assert(SCIPvarIsBinary(var));
666
667 if( SCIPvarGetUbGlobal(var) < 0.5 )
668 {
669 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
670 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
671 }
672 else
673 {
674 SCIP_VAR* repvar;
675 SCIP_Bool negated;
676
677 /* get binary representative of variable */
678 SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
679
680 /* check, if the variable should be replaced with the representative */
681 if( repvar != var )
682 {
683 /* delete old (aggregated) variable */
684 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
685
686 /* add representative instead */
687 SCIP_CALL( addCoef(scip, cons, eventhdlr, repvar) );
688 }
689 else
690 ++v;
691 }
692 }
693
694 SCIPdebugMsg(scip, "after fixings: ");
695 SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL)) );
696 SCIPdebugMsgPrint(scip, "\n");
697
698 return SCIP_OKAY;
699}
700
701/** creates LP rows corresponding to or constraint:
702 * - for each operator variable vi: resvar - vi >= 0
703 * - one additional row: resvar - v1 - ... - vn <= 0
704 */
705static
707 SCIP* scip, /**< SCIP data structure */
708 SCIP_CONS* cons /**< constraint to check */
709 )
710{
711 SCIP_CONSDATA* consdata;
712 char rowname[SCIP_MAXSTRLEN];
713 int nvars;
714 int i;
715
716 consdata = SCIPconsGetData(cons);
717 assert(consdata != NULL);
718 assert(consdata->rows == NULL);
719
720 nvars = consdata->nvars;
721
722 /* get memory for rows */
723 consdata->rowssize = consdataGetNRows(consdata);
724 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->rows, consdata->rowssize) );
725 assert(consdata->rowssize == nvars+1);
726
727 /* create operator rows */
728 for( i = 0; i < nvars; ++i )
729 {
730 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), i);
731 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[i], cons, rowname, 0.0, SCIPinfinity(scip),
733 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i], consdata->resvar, 1.0) );
734 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i], consdata->vars[i], -1.0) );
735 }
736
737 /* create additional row */
738 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
739 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[nvars], cons, rowname, -SCIPinfinity(scip), 0.0,
741 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[nvars], consdata->resvar, 1.0) );
742 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[nvars], nvars, consdata->vars, -1.0) );
743
744 return SCIP_OKAY;
745}
746
747/** adds linear relaxation of or constraint to the LP */
748static
750 SCIP* scip, /**< SCIP data structure */
751 SCIP_CONS* cons, /**< constraint to check */
752 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
753 )
754{
755 SCIP_CONSDATA* consdata;
756 int r;
757 int nrows;
758
759 consdata = SCIPconsGetData(cons);
760 assert(consdata != NULL);
761
762 if( consdata->rows == NULL )
763 {
765 }
766 assert( consdata->rows != NULL );
767
768 nrows = consdataGetNRows(consdata);
769
770 for( r = 0; r < nrows && !(*infeasible); ++r )
771 {
772 if( !SCIProwIsInLP(consdata->rows[r]) )
773 {
774 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, infeasible) );
775 }
776 }
777
778 return SCIP_OKAY;
779}
780
781/** checks or constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
782static
784 SCIP* scip, /**< SCIP data structure */
785 SCIP_CONS* cons, /**< constraint to check */
786 SCIP_SOL* sol, /**< solution to check, NULL for current solution */
787 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
788 SCIP_Bool printreason, /**< Should the reason for the violation be printed? */
789 SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
790 )
791{
792 SCIP_CONSDATA* consdata;
793 SCIP_Bool mustcheck;
794 int r;
795
796 assert(violated != NULL);
797
798 consdata = SCIPconsGetData(cons);
799 assert(consdata != NULL);
800
801 *violated = FALSE;
802
803 /* check, if we can skip this feasibility check, because all rows are in the LP and doesn't have to be checked */
804 mustcheck = checklprows;
805 mustcheck = mustcheck || (consdata->rows == NULL);
806 if( !mustcheck )
807 {
808 int nrows;
809
810 assert(consdata->rows != NULL);
811
812 nrows = consdataGetNRows(consdata);
813
814 for( r = 0; r < nrows; ++r )
815 {
816 mustcheck = !SCIProwIsInLP(consdata->rows[r]);
817 if( mustcheck )
818 break;
819 }
820 }
821
822 /* check feasibility of constraint if necessary */
823 if( mustcheck )
824 {
825 SCIP_Real maxsolval = 0.0;
826 SCIP_Real sumsolval = 0.0;
827 SCIP_Real solval;
828 SCIP_Real viol;
829 int maxsolind = 0;
830 int i;
831
832 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
833 * enforcement
834 */
835 if( sol == NULL )
836 {
837 SCIP_CALL( SCIPincConsAge(scip, cons) );
838 }
839
840 /* evaluate operator variables */
841 for( i = 0; i < consdata->nvars; ++i )
842 {
843 solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
844
845 if( maxsolval < solval )
846 {
847 maxsolind = i;
848 maxsolval = solval;
849 }
850
851 sumsolval += solval;
852 }
853
854 /* the resultant must be at least as large as every operator
855 * and at most as large as the sum of operators
856 */
857 solval = SCIPgetSolVal(scip, sol, consdata->resvar);
858 viol = MAX3(0.0, maxsolval - solval, solval - sumsolval);
859
860 if( SCIPisFeasPositive(scip, viol) )
861 {
862 *violated = TRUE;
863
864 /* only reset constraint age if we are in enforcement */
865 if( sol == NULL )
866 {
868 }
869
870 if( printreason )
871 {
872 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
873 SCIPinfoMessage(scip, NULL, ";\n");
874 SCIPinfoMessage(scip, NULL, "violation:");
875
876 if( SCIPisFeasPositive(scip, maxsolval - solval) )
877 {
878 SCIPinfoMessage(scip, NULL, " operand <%s> = TRUE and resultant <%s> = FALSE\n",
879 SCIPvarGetName(consdata->vars[maxsolind]), SCIPvarGetName(consdata->resvar));
880 }
881 else
882 {
883 SCIPinfoMessage(scip, NULL, " all operands are FALSE and resultant <%s> = TRUE\n",
884 SCIPvarGetName(consdata->resvar));
885 }
886 }
887 }
888
889 /* update constraint violation in solution */
890 if( sol != NULL )
891 SCIPupdateSolConsViolation(scip, sol, viol, viol);
892 }
893
894 return SCIP_OKAY;
895}
896
897/** separates current LP solution */
898static
900 SCIP* scip, /**< SCIP data structure */
901 SCIP_CONS* cons, /**< constraint to check */
902 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
903 SCIP_Bool* separated /**< pointer to store whether a cut was found */
904 )
905{
906 SCIP_CONSDATA* consdata;
907 SCIP_Real feasibility;
908 int r;
909 int nrows;
910
911 assert(separated != NULL);
912
913 consdata = SCIPconsGetData(cons);
914 assert(consdata != NULL);
915
916 *separated = FALSE;
917
918 /* create all necessary rows for the linear relaxation */
919 if( consdata->rows == NULL )
920 {
922 }
923 assert(consdata->rows != NULL);
924
925 nrows = consdataGetNRows(consdata);
926
927 /* test all rows for feasibility and add infeasible rows */
928 for( r = 0; r < nrows; ++r )
929 {
930 if( !SCIProwIsInLP(consdata->rows[r]) )
931 {
932 feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
933 if( SCIPisFeasNegative(scip, feasibility) )
934 {
935 SCIP_Bool infeasible;
936
937 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, &infeasible) );
938 assert( ! infeasible );
939 *separated = TRUE;
940 }
941 }
942 }
943
944 return SCIP_OKAY;
945}
946
947/** analyzes conflicting FALSE assignment to resultant of given constraint, and adds conflict constraint to problem */
948static
950 SCIP* scip, /**< SCIP data structure */
951 SCIP_CONS* cons, /**< or constraint that detected the conflict */
952 int truepos /**< position of operand that is fixed to TRUE */
953 )
954{
955 SCIP_CONSDATA* consdata;
956
957 /* conflict analysis can only be applied in solving stage and if it is applicable */
959 return SCIP_OKAY;
960
961 consdata = SCIPconsGetData(cons);
962 assert(consdata != NULL);
963 assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
964 assert(0 <= truepos && truepos < consdata->nvars);
965 assert(SCIPvarGetLbLocal(consdata->vars[truepos]) > 0.5);
966
967 /* initialize conflict analysis, and add resultant and single operand variable to conflict candidate queue */
969
970 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
971 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[truepos]) );
972
973 /* analyze the conflict */
975
976 return SCIP_OKAY;
977}
978
979/** analyzes conflicting TRUE assignment to resultant of given constraint, and adds conflict constraint to problem */
980static
982 SCIP* scip, /**< SCIP data structure */
983 SCIP_CONS* cons /**< or constraint that detected the conflict */
984 )
985{
986 SCIP_CONSDATA* consdata;
987 int v;
988
989 assert(!SCIPconsIsModifiable(cons));
990
991 /* conflict analysis can only be applied in solving stage and if it is applicable */
993 return SCIP_OKAY;
994
995 consdata = SCIPconsGetData(cons);
996 assert(consdata != NULL);
997 assert(SCIPvarGetLbLocal(consdata->resvar) > 0.5);
998
999 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1001
1002 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1003 for( v = 0; v < consdata->nvars; ++v )
1004 {
1005 assert(SCIPvarGetUbLocal(consdata->vars[v]) < 0.5);
1006 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
1007 }
1008
1009 /* analyze the conflict */
1011
1012 return SCIP_OKAY;
1013}
1014
1015/** propagates constraint with the following rules:
1016 * (1) v_i = TRUE => r = TRUE
1017 * (2) r = FALSE => v_i = FALSE for all i
1018 * (3) v_i = FALSE for all i => r = FALSE
1019 * (4) r = TRUE, v_i = FALSE for all i except j => v_j = TRUE
1020 */
1021static
1023 SCIP* scip, /**< SCIP data structure */
1024 SCIP_CONS* cons, /**< or constraint to be processed */
1025 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1026 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1027 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1028 )
1029{
1030 SCIP_CONSDATA* consdata;
1031 SCIP_VAR* resvar;
1032 SCIP_VAR** vars;
1033 int nvars;
1034 int watchedvar1;
1035 int watchedvar2;
1036 int i;
1037 SCIP_Bool infeasible;
1038 SCIP_Bool tightened;
1039
1040 assert(cutoff != NULL);
1041 assert(nfixedvars != NULL);
1042
1043 consdata = SCIPconsGetData(cons);
1044 assert(consdata != NULL);
1045
1046 resvar = consdata->resvar;
1047 vars = consdata->vars;
1048 nvars = consdata->nvars;
1049
1050 /* don't process the constraint, if none of the operator variables was fixed to TRUE, and if the watched variables
1051 * and the resultant weren't fixed to any value since last propagation call
1052 */
1053 if( consdata->propagated )
1054 {
1055 assert(consdata->nofixedone);
1056 assert(SCIPisFeasEQ(scip, SCIPvarGetUbLocal(resvar), 1.0));
1057 return SCIP_OKAY;
1058 }
1059
1060 /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
1062 {
1063 SCIP_CALL( SCIPincConsAge(scip, cons) );
1064 }
1065
1066 /* if one of the operator variables was fixed to TRUE, the resultant can be fixed to TRUE (rule (1)) */
1067 if( !consdata->nofixedone )
1068 {
1069 for( i = 0; i < nvars && SCIPvarGetLbLocal(vars[i]) < 0.5; ++i ) /* search fixed operator */
1070 {}
1071 if( i < nvars )
1072 {
1073 SCIPdebugMsg(scip, "constraint <%s>: operator var <%s> fixed to 1.0 -> fix resultant <%s> to 1.0\n",
1074 SCIPconsGetName(cons), SCIPvarGetName(vars[i]), SCIPvarGetName(resvar));
1075 SCIP_CALL( SCIPinferBinvarCons(scip, resvar, TRUE, cons, (int)PROPRULE_1, &infeasible, &tightened) );
1076 if( infeasible )
1077 {
1078 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1079 SCIP_CALL( analyzeConflictZero(scip, cons, i) );
1081 *cutoff = TRUE;
1082 }
1083 else
1084 {
1086 if( tightened )
1087 {
1089 (*nfixedvars)++;
1090 }
1091 }
1092
1093 return SCIP_OKAY;
1094 }
1095 else
1096 consdata->nofixedone = TRUE;
1097 }
1098 assert(consdata->nofixedone);
1099
1100 /* if resultant is fixed to FALSE, all operator variables can be fixed to FALSE (rule (2)) */
1101 if( SCIPvarGetUbLocal(resvar) < 0.5 )
1102 {
1103 for( i = 0; i < nvars && !(*cutoff); ++i )
1104 {
1105 SCIPdebugMsg(scip, "constraint <%s>: resultant var <%s> fixed to 0.0 -> fix operator var <%s> to 0.0\n",
1106 SCIPconsGetName(cons), SCIPvarGetName(resvar), SCIPvarGetName(vars[i]));
1107 SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], FALSE, cons, (int)PROPRULE_2, &infeasible, &tightened) );
1108 if( infeasible )
1109 {
1110 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1111 SCIP_CALL( analyzeConflictZero(scip, cons, i) );
1113 *cutoff = TRUE;
1114 }
1115 else if( tightened )
1116 {
1118 (*nfixedvars)++;
1119 }
1120 }
1121
1122 if( !(*cutoff) )
1123 {
1125 }
1126
1127 return SCIP_OKAY;
1128 }
1129
1130 /* rules (3) and (4) can only be applied, if we know all operator variables */
1131 if( SCIPconsIsModifiable(cons) )
1132 return SCIP_OKAY;
1133
1134 /* rules (3) and (4) cannot be applied, if we have at least two unfixed variables left;
1135 * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
1136 * if these ones get fixed
1137 */
1138 watchedvar1 = consdata->watchedvar1;
1139 watchedvar2 = consdata->watchedvar2;
1140
1141 /* check, if watched variables are still unfixed */
1142 if( watchedvar1 != -1 )
1143 {
1144 assert(SCIPvarGetLbLocal(vars[watchedvar1]) < 0.5); /* otherwise, rule (1) could be applied */
1145 if( SCIPvarGetUbLocal(vars[watchedvar1]) < 0.5 )
1146 watchedvar1 = -1;
1147 }
1148 if( watchedvar2 != -1 )
1149 {
1150 assert(SCIPvarGetLbLocal(vars[watchedvar2]) < 0.5); /* otherwise, rule (1) could be applied */
1151 if( SCIPvarGetUbLocal(vars[watchedvar2]) < 0.5 )
1152 watchedvar2 = -1;
1153 }
1154
1155 /* if only one watched variable is still unfixed, make it the first one */
1156 if( watchedvar1 == -1 )
1157 {
1158 watchedvar1 = watchedvar2;
1159 watchedvar2 = -1;
1160 }
1161 assert(watchedvar1 != -1 || watchedvar2 == -1);
1162
1163 /* if the watched variables are invalid (fixed), find new ones if existing */
1164 if( watchedvar2 == -1 )
1165 {
1166 for( i = 0; i < nvars; ++i )
1167 {
1168 assert(SCIPvarGetLbLocal(vars[i]) < 0.5); /* otherwise, rule (1) could be applied */
1169 if( SCIPvarGetUbLocal(vars[i]) > 0.5 )
1170 {
1171 if( watchedvar1 == -1 )
1172 {
1173 assert(watchedvar2 == -1);
1174 watchedvar1 = i;
1175 }
1176 else if( watchedvar1 != i )
1177 {
1178 watchedvar2 = i;
1179 break;
1180 }
1181 }
1182 }
1183 }
1184 assert(watchedvar1 != -1 || watchedvar2 == -1);
1185
1186 /* if all variables are fixed to FALSE, the resultant can also be fixed to FALSE (rule (3)) */
1187 if( watchedvar1 == -1 )
1188 {
1189 assert(watchedvar2 == -1);
1190
1191 SCIPdebugMsg(scip, "constraint <%s>: all operator vars fixed to 0.0 -> fix resultant <%s> to 0.0\n",
1192 SCIPconsGetName(cons), SCIPvarGetName(resvar));
1193 SCIP_CALL( SCIPinferBinvarCons(scip, resvar, FALSE, cons, (int)PROPRULE_3, &infeasible, &tightened) );
1194 if( infeasible )
1195 {
1196 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1199 *cutoff = TRUE;
1200 }
1201 else
1202 {
1204 if( tightened )
1205 {
1207 (*nfixedvars)++;
1208 }
1209 }
1210
1211 return SCIP_OKAY;
1212 }
1213
1214 /* if resultant is fixed to TRUE, and only one operator variable is not fixed to FALSE, this operator variable
1215 * can be fixed to TRUE (rule (4))
1216 */
1217 if( SCIPvarGetLbLocal(resvar) > 0.5 && watchedvar2 == -1 )
1218 {
1219 assert(watchedvar1 != -1);
1220
1221 SCIPdebugMsg(scip, "constraint <%s>: resultant <%s> fixed to 1.0, only one unfixed operand -> fix operand <%s> to 1.0\n",
1222 SCIPconsGetName(cons), SCIPvarGetName(resvar), SCIPvarGetName(vars[watchedvar1]));
1223 SCIP_CALL( SCIPinferBinvarCons(scip, vars[watchedvar1], TRUE, cons, (int)PROPRULE_4, &infeasible, &tightened) );
1224 if( infeasible )
1225 {
1226 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1229 *cutoff = TRUE;
1230 }
1231 else
1232 {
1234 if( tightened )
1235 {
1237 (*nfixedvars)++;
1238 }
1239 }
1240
1241 return SCIP_OKAY;
1242 }
1243
1244 /* switch to the new watched variables */
1245 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
1246
1247 /* mark the constraint propagated */
1248 consdata->propagated = TRUE;
1249
1250 return SCIP_OKAY;
1251}
1252
1253/** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
1254 * propagation rule (see propagateCons()):
1255 * (1) v_i = TRUE => r = TRUE
1256 * (2) r = FALSE => v_i = FALSE for all i
1257 * (3) v_i = FALSE for all i => r = FALSE
1258 * (4) r = TRUE, v_i = FALSE for all i except j => v_j = TRUE
1259 */
1260static
1262 SCIP* scip, /**< SCIP data structure */
1263 SCIP_CONS* cons, /**< constraint that inferred the bound change */
1264 SCIP_VAR* infervar, /**< variable that was deduced */
1265 PROPRULE proprule, /**< propagation rule that deduced the value */
1266 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1267 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1268 )
1269{
1270 SCIP_CONSDATA* consdata;
1271 SCIP_VAR** vars;
1272 int nvars;
1273 int i;
1274
1275 assert(result != NULL);
1276
1277 consdata = SCIPconsGetData(cons);
1278 assert(consdata != NULL);
1279 vars = consdata->vars;
1280 nvars = consdata->nvars;
1281
1282 switch( proprule )
1283 {
1284 case PROPRULE_1:
1285 /* the resultant was inferred to TRUE, because one operand variable was TRUE */
1286 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1287 assert(infervar == consdata->resvar);
1288 for( i = 0; i < nvars; ++i )
1289 {
1290 if( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
1291 {
1293 break;
1294 }
1295 }
1296 assert(i < nvars);
1297 *result = SCIP_SUCCESS;
1298 break;
1299
1300 case PROPRULE_2:
1301 /* the operand variable was inferred to FALSE, because the resultant was FALSE */
1302 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
1303 assert(SCIPgetVarUbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) < 0.5);
1304 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1305 *result = SCIP_SUCCESS;
1306 break;
1307
1308 case PROPRULE_3:
1309 /* the resultant was inferred to FALSE, because all operand variables were FALSE */
1310 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
1311 assert(infervar == consdata->resvar);
1312 for( i = 0; i < nvars; ++i )
1313 {
1314 assert(SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5);
1316 }
1317 *result = SCIP_SUCCESS;
1318 break;
1319
1320 case PROPRULE_4:
1321 /* the operand variable was inferred to TRUE, because the resultant was TRUE and all other operands were FALSE */
1322 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1323 assert(SCIPgetVarLbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) > 0.5);
1324 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1325 for( i = 0; i < nvars; ++i )
1326 {
1327 if( vars[i] != infervar )
1328 {
1329 assert(SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5);
1331 }
1332 }
1333 *result = SCIP_SUCCESS;
1334 break;
1335
1336 case PROPRULE_INVALID:
1337 default:
1338 SCIPerrorMessage("invalid inference information %d in or constraint <%s>\n", proprule, SCIPconsGetName(cons));
1339 return SCIP_INVALIDDATA;
1340 }
1341
1342 return SCIP_OKAY;
1343}
1344
1345/** upgrades unmodifiable or constraint into an and constraint on negated variables */
1346static
1348 SCIP* scip, /**< SCIP data structure */
1349 SCIP_CONS* cons, /**< constraint that inferred the bound change */
1350 int* nupgdconss /**< pointer to count the number of constraint upgrades */
1351 )
1352{
1353 SCIP_CONSDATA* consdata;
1354 SCIP_VAR** negvars;
1355 SCIP_VAR* negresvar;
1356 SCIP_CONS* andcons;
1357 int i;
1358
1359 assert(nupgdconss != NULL);
1360
1361 /* we cannot upgrade a modifiable constraint, since we don't know what additional variables to expect */
1362 if( SCIPconsIsModifiable(cons) )
1363 return SCIP_OKAY;
1364
1365 SCIPdebugMsg(scip, "upgrading or constraint <%s> into equivalent and constraint on negated variables\n",
1366 SCIPconsGetName(cons));
1367
1368 consdata = SCIPconsGetData(cons);
1369 assert(consdata != NULL);
1370
1371 /* get the negated versions of the variables */
1372 SCIP_CALL( SCIPallocBufferArray(scip, &negvars, consdata->nvars) );
1373 for( i = 0; i < consdata->nvars; ++i )
1374 {
1375 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[i], &negvars[i]) );
1376 }
1377 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->resvar, &negresvar) );
1378
1379 /* create and add the and constraint */
1380 SCIP_CALL( SCIPcreateConsAnd(scip, &andcons, SCIPconsGetName(cons), negresvar, consdata->nvars, negvars,
1384 SCIP_CALL( SCIPaddCons(scip, andcons) );
1385 SCIP_CALL( SCIPreleaseCons(scip, &andcons) );
1386
1387 /* delete the or constraint */
1388 SCIP_CALL( SCIPdelCons(scip, cons) );
1389
1390 /* free temporary memory */
1391 SCIPfreeBufferArray(scip, &negvars);
1392
1393 (*nupgdconss)++;
1394
1395 return SCIP_OKAY;
1396}
1397
1398/** adds symmetry information of constraint to a symmetry detection graph */
1399static
1401 SCIP* scip, /**< SCIP pointer */
1402 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */
1403 SCIP_CONS* cons, /**< constraint */
1404 SYM_GRAPH* graph, /**< symmetry detection graph */
1405 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */
1406 )
1407{
1408 SCIP_CONSDATA* consdata;
1409 SCIP_VAR** orvars;
1410 SCIP_VAR** vars;
1411 SCIP_Real* vals;
1412 SCIP_Real constant;
1413 int consnodeidx;
1414 int ornodeidx;
1415 int nlocvars;
1416 int i;
1417
1418 assert(scip != NULL);
1419 assert(cons != NULL);
1420 assert(graph != NULL);
1421 assert(success != NULL);
1422
1423 consdata = SCIPconsGetData(cons);
1424 assert(consdata != NULL);
1425
1426 /* create arrays to store active representation of variables */
1427 nlocvars = 1;
1428 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nlocvars) );
1429 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nlocvars) );
1430
1431 /* add constraint node */
1432 SCIP_CALL( SCIPaddSymgraphConsnode(scip, graph, cons, 0.0, 0.0, &consnodeidx) );
1433
1434 /* add resultant to symmetry detection graph */
1435 assert(consdata->resvar != NULL);
1436 vars[0] = consdata->resvar;
1437 vals[0] = 1.0;
1438 constant = 0.0;
1439 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
1440 SCIP_CALL( SCIPaddSymgraphVarAggregation(scip, graph, consnodeidx, vars, vals, nlocvars, constant) );
1441
1442 /* add node modeling the OR-part and connect it with constraint node */
1443 SCIP_CALL( SCIPaddSymgraphOpnode(scip, graph, (int)SYM_CONSOPTYPE_OR, &ornodeidx) );
1444 SCIP_CALL( SCIPaddSymgraphEdge(scip, graph, consnodeidx, ornodeidx, FALSE, 0.0) );
1445
1446 /* add variables */
1447 orvars = consdata->vars;
1448 for( i = 0; i < consdata->nvars; ++i )
1449 {
1450 assert(orvars[i] != NULL);
1451 vars[0] = orvars[i];
1452 vals[0] = 1.0;
1453 constant = 0.0;
1454 nlocvars = 1;
1455 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
1456 SCIP_CALL( SCIPaddSymgraphVarAggregation(scip, graph, ornodeidx, vars, vals, nlocvars, constant) );
1457 }
1458
1459 SCIPfreeBufferArray(scip, &vals);
1460 SCIPfreeBufferArray(scip, &vars);
1461
1462 *success = TRUE;
1463
1464 return SCIP_OKAY;
1465}
1466
1467/*
1468 * Callback methods of constraint handler
1469 */
1470
1471/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1472static
1474{ /*lint --e{715}*/
1475 assert(scip != NULL);
1476 assert(conshdlr != NULL);
1477 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1478
1479 /* call inclusion method of constraint handler */
1481
1482 *valid = TRUE;
1483
1484 return SCIP_OKAY;
1485}
1486
1487/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1488static
1490{ /*lint --e{715}*/
1491 SCIP_CONSHDLRDATA* conshdlrdata;
1492
1493 /* free constraint handler data */
1494 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1495 assert(conshdlrdata != NULL);
1496
1497 conshdlrdataFree(scip, &conshdlrdata);
1498
1499 SCIPconshdlrSetData(conshdlr, NULL);
1500
1501 return SCIP_OKAY;
1502}
1503
1504
1505/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
1506static
1508{ /*lint --e{715}*/
1509 SCIP_CONSDATA* consdata;
1510 int c;
1511
1512 /* release and free the rows of all constraints */
1513 for( c = 0; c < nconss; ++c )
1514 {
1515 consdata = SCIPconsGetData(conss[c]);
1516 SCIP_CALL( consdataFreeRows(scip, consdata) );
1517 }
1518
1519 return SCIP_OKAY;
1520}
1521
1522
1523/** frees specific constraint data */
1524static
1526{ /*lint --e{715}*/
1527 SCIP_CONSHDLRDATA* conshdlrdata;
1528
1529 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1530 assert(conshdlrdata != NULL);
1531
1532 SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
1533
1534 return SCIP_OKAY;
1535}
1536
1537
1538/** transforms constraint data into data belonging to the transformed problem */
1539static
1541{ /*lint --e{715}*/
1542 SCIP_CONSHDLRDATA* conshdlrdata;
1543 SCIP_CONSDATA* sourcedata;
1544 SCIP_CONSDATA* targetdata;
1545
1546 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1547 assert(conshdlrdata != NULL);
1548
1549 sourcedata = SCIPconsGetData(sourcecons);
1550 assert(sourcedata != NULL);
1551
1552 /* create target constraint data */
1553 SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
1554 sourcedata->nvars, sourcedata->vars, sourcedata->resvar) );
1555
1556 /* create target constraint */
1557 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1558 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1559 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
1560 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
1561 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1562
1563 return SCIP_OKAY;
1564}
1565
1566
1567/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1568static
1570{ /*lint --e{715}*/
1571 int i;
1572
1573 *infeasible = FALSE;
1574
1575 for( i = 0; i < nconss && !(*infeasible); i++ )
1576 {
1577 assert(SCIPconsIsInitial(conss[i]));
1578 SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
1579 }
1580
1581 return SCIP_OKAY;
1582}
1583
1584
1585/** separation method of constraint handler for LP solutions */
1586static
1588{ /*lint --e{715}*/
1589 SCIP_Bool separated;
1590 int c;
1591
1592 *result = SCIP_DIDNOTFIND;
1593
1594 /* separate all useful constraints */
1595 for( c = 0; c < nusefulconss; ++c )
1596 {
1597 SCIP_CALL( separateCons(scip, conss[c], NULL, &separated) );
1598 if( separated )
1599 *result = SCIP_SEPARATED;
1600 }
1601
1602 /* combine constraints to get more cuts */
1603 /**@todo combine constraints to get further cuts */
1604
1605 return SCIP_OKAY;
1606}
1607
1608
1609/** separation method of constraint handler for arbitrary primal solutions */
1610static
1612{ /*lint --e{715}*/
1613 SCIP_Bool separated;
1614 int c;
1615
1616 *result = SCIP_DIDNOTFIND;
1617
1618 /* separate all useful constraints */
1619 for( c = 0; c < nusefulconss; ++c )
1620 {
1621 SCIP_CALL( separateCons(scip, conss[c], sol, &separated) );
1622 if( separated )
1623 *result = SCIP_SEPARATED;
1624 }
1625
1626 /* combine constraints to get more cuts */
1627 /**@todo combine constraints to get further cuts */
1628
1629 return SCIP_OKAY;
1630}
1631
1632
1633/** constraint enforcing method of constraint handler for LP solutions */
1634static
1636{ /*lint --e{715}*/
1637 SCIP_Bool violated;
1638 int i;
1639
1640 /* method is called only for integral solutions, because the enforcing priority is negative */
1641 for( i = 0; i < nconss; i++ )
1642 {
1643 SCIP_CALL( checkCons(scip, conss[i], NULL, FALSE, FALSE, &violated) );
1644 if( violated )
1645 {
1646 SCIP_Bool separated;
1647
1648 SCIP_CALL( separateCons(scip, conss[i], NULL, &separated) );
1649
1650 /* if the solution is integral, the separation always finds a cut
1651 * if some implicit binary variable is not integral, then some other constraint needs to be enforced first
1652 */
1653 if( separated )
1654 *result = SCIP_SEPARATED;
1655 else
1656 *result = SCIP_INFEASIBLE;
1657
1658 return SCIP_OKAY;
1659 }
1660 }
1661 *result = SCIP_FEASIBLE;
1662
1663 return SCIP_OKAY;
1664}
1665
1666
1667/** constraint enforcing method of constraint handler for relaxation solutions */
1668static
1670{ /*lint --e{715}*/
1671 SCIP_Bool violated;
1672 int i;
1673
1674 /* method is called only for integral solutions, because the enforcing priority is negative */
1675 for( i = 0; i < nconss; i++ )
1676 {
1677 SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
1678 if( violated )
1679 {
1680 SCIP_Bool separated;
1681
1682 SCIP_CALL( separateCons(scip, conss[i], sol, &separated) );
1683
1684 /* if the solution is integral, the separation always finds a cut
1685 * if some implicit binary variable is not integral, then some other constraint needs to be enforced first
1686 */
1687 if( separated )
1688 *result = SCIP_SEPARATED;
1689 else
1690 *result = SCIP_INFEASIBLE;
1691
1692 return SCIP_OKAY;
1693 }
1694 }
1695 *result = SCIP_FEASIBLE;
1696
1697 return SCIP_OKAY;
1698}
1699
1700
1701/** constraint enforcing method of constraint handler for pseudo solutions */
1702static
1704{ /*lint --e{715}*/
1705 SCIP_Bool violated;
1706 int i;
1707
1708 /* method is called only for integral solutions, because the enforcing priority is negative */
1709 for( i = 0; i < nconss; i++ )
1710 {
1711 SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
1712 if( violated )
1713 {
1714 *result = SCIP_INFEASIBLE;
1715 return SCIP_OKAY;
1716 }
1717 }
1718 *result = SCIP_FEASIBLE;
1719
1720 return SCIP_OKAY;
1721}
1722
1723/** feasibility check method of constraint handler or */
1724static
1726{ /*lint --e{715}*/
1727 SCIP_Bool violated;
1728 int i;
1729
1730 *result = SCIP_FEASIBLE;
1731
1732 for( i = 0; i < nconss && ( *result == SCIP_FEASIBLE || completely ); ++i )
1733 {
1734 SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
1735 if( violated )
1736 *result = SCIP_INFEASIBLE;
1737 }
1738
1739 return SCIP_OKAY;
1740}
1741
1742/** domain propagation method of constraint handler */
1743static
1745{ /*lint --e{715}*/
1746 SCIP_CONSHDLRDATA* conshdlrdata;
1747 SCIP_Bool cutoff;
1748 int nfixedvars;
1749 int c;
1750
1751 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1752 assert(conshdlrdata != NULL);
1753
1754 cutoff = FALSE;
1755 nfixedvars = 0;
1756
1757 /* propagate all useful constraints */
1758 for( c = 0; c < nusefulconss && !cutoff; ++c )
1759 {
1760 SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars) );
1761 }
1762
1763 /* return the correct result */
1764 if( cutoff )
1765 *result = SCIP_CUTOFF;
1766 else if( nfixedvars > 0 )
1767 *result = SCIP_REDUCEDDOM;
1768 else
1769 *result = SCIP_DIDNOTFIND;
1770
1771 return SCIP_OKAY;
1772}
1773
1774
1775/** presolving method of constraint handler */
1776static
1778{ /*lint --e{715}*/
1779 SCIP_CONSHDLRDATA* conshdlrdata;
1780 SCIP_CONS* cons;
1781 SCIP_CONSDATA* consdata;
1782 SCIP_Bool cutoff;
1783 SCIP_Bool redundant;
1784 SCIP_Bool aggregated;
1785 int oldnfixedvars;
1786 int oldnaggrvars;
1787 int oldnupgdconss;
1788 int c;
1789
1790 assert(result != NULL);
1791
1792 *result = SCIP_DIDNOTFIND;
1793 oldnfixedvars = *nfixedvars;
1794 oldnaggrvars = *naggrvars;
1795 oldnupgdconss = *nupgdconss;
1796
1797 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1798 assert(conshdlrdata != NULL);
1799
1800 /* process constraints */
1801 cutoff = FALSE;
1802 for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
1803 {
1804 cons = conss[c];
1805 assert(cons != NULL);
1806 consdata = SCIPconsGetData(cons);
1807 assert(consdata != NULL);
1808
1809 /* force presolving the constraint in the initial round */
1810 if( nrounds == 0 )
1811 consdata->propagated = FALSE;
1812
1813 /* propagate constraint */
1814 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars) );
1815
1816 /* remove all variables that are fixed to one */
1817 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr) );
1818
1819 /* transform or constraints into and constraints on the negated variables in order to improve
1820 * the pairwise constraint presolving possibilities
1821 */
1822 SCIP_CALL( upgradeCons(scip, cons, nupgdconss) );
1823
1824 if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
1825 {
1826 assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
1827
1828 /* if only one variable is left, the resultant has to be equal to this single variable */
1829 if( consdata->nvars == 1 )
1830 {
1831 SCIPdebugMsg(scip, "or constraint <%s> has only one variable not fixed to 0.0\n", SCIPconsGetName(cons));
1832
1833 assert(consdata->vars != NULL);
1834 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
1835 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
1836
1837 /* aggregate variables: resultant - operand == 0 */
1838 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
1839 &cutoff, &redundant, &aggregated) );
1840 assert(redundant || SCIPdoNotAggr(scip));
1841
1842 if( aggregated )
1843 {
1844 assert(redundant);
1845 (*naggrvars)++;
1846 }
1847
1848 if( redundant )
1849 {
1850 /* delete constraint */
1851 SCIP_CALL( SCIPdelCons(scip, cons) );
1852 (*ndelconss)++;
1853 }
1854 }
1855 else if( !consdata->impladded )
1856 {
1857 int i;
1858
1859 /* add implications: resultant == 0 -> all operands == 0 */
1860 for( i = 0; i < consdata->nvars && !cutoff; ++i )
1861 {
1862 int nimplbdchgs;
1863
1864 SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, FALSE, consdata->vars[i],
1865 SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
1866 *nchgbds += nimplbdchgs;
1867 }
1868 consdata->impladded = TRUE;
1869 }
1870
1871 /* if in r = x or y, the resultant is fixed to one, add implication x = 0 -> y = 1 */
1872 if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
1873 && SCIPvarGetLbGlobal(consdata->resvar) > 0.5 )
1874 {
1875 int nimplbdchgs;
1876
1877 SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], FALSE, consdata->vars[1],
1878 SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
1879 (*nchgbds) += nimplbdchgs;
1880 consdata->opimpladded = TRUE;
1881 }
1882 }
1883 }
1884
1885 /* return the correct result code */
1886 if( cutoff )
1887 *result = SCIP_CUTOFF;
1888 else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nupgdconss > oldnupgdconss )
1889 *result = SCIP_SUCCESS;
1890
1891 return SCIP_OKAY;
1892}
1893
1894
1895/** propagation conflict resolving method of constraint handler */
1896static
1898{ /*lint --e{715}*/
1899 SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
1900
1901 return SCIP_OKAY;
1902}
1903
1904
1905/** variable rounding lock method of constraint handler */
1906static
1908{ /*lint --e{715}*/
1909 SCIP_CONSDATA* consdata;
1910 int i;
1911
1912 assert(locktype == SCIP_LOCKTYPE_MODEL);
1913
1914 consdata = SCIPconsGetData(cons);
1915 assert(consdata != NULL);
1916
1917 /* lock resultant variable */
1918 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->resvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
1919
1920 /* lock all operand variables */
1921 for( i = 0; i < consdata->nvars; ++i )
1922 {
1923 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
1924 }
1925
1926 return SCIP_OKAY;
1927}
1928
1929
1930/** constraint display method of constraint handler */
1931static
1933{ /*lint --e{715}*/
1934 assert( scip != NULL );
1935 assert( conshdlr != NULL );
1936 assert( cons != NULL );
1937
1939
1940 return SCIP_OKAY;
1941}
1942
1943/** constraint copying method of constraint handler */
1944static
1946{ /*lint --e{715}*/
1947 SCIP_VAR** sourcevars;
1948 SCIP_VAR** vars;
1949 SCIP_VAR* sourceresvar;
1950 SCIP_VAR* resvar;
1951 int nvars;
1952 int v;
1953
1954 assert(valid != NULL);
1955 (*valid) = TRUE;
1956 resvar = NULL;
1957
1958 /* get variables that need to be copied */
1959 sourceresvar = SCIPgetResultantOr(sourcescip, sourcecons);
1960 sourcevars = SCIPgetVarsOr(sourcescip, sourcecons);
1961 nvars = SCIPgetNVarsOr(sourcescip, sourcecons);
1962
1963 if( nvars == -1 )
1964 return SCIP_INVALIDCALL;
1965
1966 /* allocate buffer array */
1967 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1968
1969 /* map operand variables to active variables of the target SCIP */
1970 for( v = 0; v < nvars && *valid; ++v )
1971 {
1972 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
1973 assert(!(*valid) || vars[v] != NULL);
1974 }
1975
1976 /* map resultant to active variable of the target SCIP */
1977 if( *valid )
1978 {
1979 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
1980 assert(!(*valid) || resvar != NULL);
1981
1982 if( *valid )
1983 {
1984 assert(resvar != NULL);
1985 SCIP_CALL( SCIPcreateConsOr(scip, cons, SCIPconsGetName(sourcecons), resvar, nvars, vars,
1986 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1987 }
1988 }
1989
1990 /* free buffer array */
1991 SCIPfreeBufferArray(scip, &vars);
1992
1993 return SCIP_OKAY;
1994}
1995
1996/** constraint parsing method of constraint handler */
1997static
1999{ /*lint --e{715}*/
2000 SCIP_VAR** vars;
2001 SCIP_VAR* resvar;
2002 char* strcopy;
2003 char* token;
2004 char* saveptr;
2005 char* endptr;
2006 int requiredsize;
2007 int varssize;
2008 int nvars;
2009
2010 SCIPdebugMsg(scip, "parse <%s> as or constraint\n", str);
2011
2012 *success = FALSE;
2013
2014 /* copy string for truncating it */
2015 SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, str, (int)(strlen(str)+1)));
2016
2017 /* cutoff "or" form the constraint string */
2018 token = SCIPstrtok(strcopy, "=", &saveptr );
2019
2020 /* parse variable name */
2021 SCIP_CALL( SCIPparseVarName(scip, token, &resvar, &endptr) );
2022
2023 if( resvar == NULL )
2024 {
2025 SCIPerrorMessage("resultant variable does not exist\n");
2026 }
2027 else
2028 {
2029 /* cutoff "or" form the constraint string */
2030 (void) SCIPstrtok(NULL, "(", &saveptr );
2031
2032 /* cutoff ")" form the constraint string */
2033 token = SCIPstrtok(NULL, ")", &saveptr );
2034
2035 varssize = 100;
2036 nvars = 0;
2037
2038 /* allocate buffer array for variables */
2039 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
2040
2041 /* parse string */
2042 SCIP_CALL( SCIPparseVarsList(scip, token, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
2043
2044 if( *success )
2045 {
2046 /* check if the size of the variable array was great enough */
2047 if( varssize < requiredsize )
2048 {
2049 /* reallocate memory */
2050 varssize = requiredsize;
2051 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
2052
2053 /* parse string again with the correct size of the variable array */
2054 SCIP_CALL( SCIPparseVarsList(scip, token, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
2055 }
2056
2057 assert(*success);
2058 assert(varssize >= requiredsize);
2059
2060 /* create and constraint */
2061 SCIP_CALL( SCIPcreateConsOr(scip, cons, name, resvar, nvars, vars,
2062 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2063 }
2064
2065 /* free variable buffer */
2066 SCIPfreeBufferArray(scip, &vars);
2067 }
2068
2069 /* free string buffer */
2070 SCIPfreeBufferArray(scip, &strcopy);
2071
2072 return SCIP_OKAY;
2073}
2074
2075/** constraint method of constraint handler which returns the variables (if possible) */
2076static
2078{ /*lint --e{715}*/
2079 SCIP_CONSDATA* consdata;
2080
2081 consdata = SCIPconsGetData(cons);
2082 assert(consdata != NULL);
2083
2084 if( varssize < consdata->nvars + 1 )
2085 (*success) = FALSE;
2086 else
2087 {
2088 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
2089 vars[consdata->nvars] = consdata->resvar;
2090 (*success) = TRUE;
2091 }
2092
2093 return SCIP_OKAY;
2094}
2095
2096/** constraint method of constraint handler which returns the number of variable (if possible) */
2097static
2099{ /*lint --e{715}*/
2100 SCIP_CONSDATA* consdata;
2101
2102 assert(cons != NULL);
2103
2104 consdata = SCIPconsGetData(cons);
2105 assert(consdata != NULL);
2106
2107 (*nvars) = consdata->nvars + 1;
2108 (*success) = TRUE;
2109
2110 return SCIP_OKAY;
2111}
2112
2113/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
2114static
2115SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphOr)
2116{ /*lint --e{715}*/
2117 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) );
2118
2119 return SCIP_OKAY;
2120}
2121
2122/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
2123static
2124SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphOr)
2125{ /*lint --e{715}*/
2126 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) );
2127
2128 return SCIP_OKAY;
2129}
2130
2131/*
2132 * Callback methods of event handler
2133 */
2134
2135static
2137{ /*lint --e{715}*/
2138 SCIP_CONSDATA* consdata;
2139
2140 assert(eventhdlr != NULL);
2141 assert(eventdata != NULL);
2142 assert(event != NULL);
2143
2144 consdata = (SCIP_CONSDATA*)eventdata;
2145 assert(consdata != NULL);
2146
2147 /* check, if the variable was fixed to one */
2149 consdata->nofixedone = FALSE;
2150
2151 consdata->propagated = FALSE;
2152
2153 return SCIP_OKAY;
2154}
2155
2156
2157/*
2158 * constraint specific interface methods
2159 */
2160
2161/** creates the handler for or constraints and includes it in SCIP */
2163 SCIP* scip /**< SCIP data structure */
2164 )
2165{
2166 SCIP_CONSHDLRDATA* conshdlrdata;
2167 SCIP_CONSHDLR* conshdlr;
2168 SCIP_EVENTHDLR* eventhdlr;
2169
2170 /* create event handler for events on variables */
2172 eventExecOr, NULL) );
2173
2174 /* create constraint handler data */
2175 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
2176
2177 /* include constraint handler */
2180 consEnfolpOr, consEnfopsOr, consCheckOr, consLockOr,
2181 conshdlrdata) );
2182 assert(conshdlr != NULL);
2183
2184 /* set non-fundamental callbacks via specific setter functions */
2185 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOr, consCopyOr) );
2186 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOr) );
2187 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolOr) );
2188 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOr) );
2189 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOr) );
2190 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOr) );
2191 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOr) );
2192 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOr) );
2194 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOr) );
2197 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOr) );
2198 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOr, consSepasolOr, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY,
2200 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOr) );
2201 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOr) );
2202 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphOr) );
2203 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphOr) );
2204
2205 return SCIP_OKAY;
2206}
2207
2208/** creates and captures an or constraint
2209 *
2210 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2211 */
2213 SCIP* scip, /**< SCIP data structure */
2214 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2215 const char* name, /**< name of constraint */
2216 SCIP_VAR* resvar, /**< resultant variable of the operation */
2217 int nvars, /**< number of operator variables in the constraint */
2218 SCIP_VAR** vars, /**< array with operator variables of constraint */
2219 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2220 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2221 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2222 * Usually set to TRUE. */
2223 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2224 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2225 SCIP_Bool check, /**< should the constraint be checked for feasibility?
2226 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2227 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2228 * Usually set to TRUE. */
2229 SCIP_Bool local, /**< is constraint only valid locally?
2230 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2231 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2232 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2233 * adds coefficients to this constraint. */
2234 SCIP_Bool dynamic, /**< is constraint subject to aging?
2235 * Usually set to FALSE. Set to TRUE for own cuts which
2236 * are separated as constraints. */
2237 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2238 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2239 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2240 * if it may be moved to a more global node?
2241 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2242 )
2243{
2244 SCIP_CONSHDLR* conshdlr;
2245 SCIP_CONSHDLRDATA* conshdlrdata;
2246 SCIP_CONSDATA* consdata;
2247
2248 /* find the or constraint handler */
2249 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2250 if( conshdlr == NULL )
2251 {
2252 SCIPerrorMessage("or constraint handler not found\n");
2253 return SCIP_PLUGINNOTFOUND;
2254 }
2255
2256 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2257 assert(conshdlrdata != NULL);
2258
2259 /* create constraint data */
2260 SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar) );
2261
2262 /* create constraint */
2263 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2264 local, modifiable, dynamic, removable, stickingatnode) );
2265
2266 return SCIP_OKAY;
2267}
2268
2269/** creates and captures an or constraint
2270 * in its most basic variant, i. e., with all constraint flags set to their default values
2271 *
2272 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2273 */
2275 SCIP* scip, /**< SCIP data structure */
2276 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2277 const char* name, /**< name of constraint */
2278 SCIP_VAR* resvar, /**< resultant variable of the operation */
2279 int nvars, /**< number of operator variables in the constraint */
2280 SCIP_VAR** vars /**< array with operator variables of constraint */
2281 )
2282{
2283 SCIP_CALL( SCIPcreateConsOr(scip, cons, name, resvar, nvars, vars, TRUE, TRUE, TRUE, TRUE, TRUE,
2284 FALSE, FALSE, FALSE, FALSE, FALSE) );
2285
2286 return SCIP_OKAY;
2287}
2288
2289/** gets number of variables in or constraint */
2291 SCIP* scip, /**< SCIP data structure */
2292 SCIP_CONS* cons /**< constraint data */
2293 )
2294{
2295 SCIP_CONSDATA* consdata;
2296
2297 assert(scip != NULL);
2298
2299 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2300 {
2301 SCIPerrorMessage("constraint is not an or constraint\n");
2302 SCIPABORT();
2303 return -1; /*lint !e527*/
2304 }
2305
2306 consdata = SCIPconsGetData(cons);
2307 assert(consdata != NULL);
2308
2309 return consdata->nvars;
2310}
2311
2312/** gets array of variables in or constraint */
2314 SCIP* scip, /**< SCIP data structure */
2315 SCIP_CONS* cons /**< constraint data */
2316 )
2317{
2318 SCIP_CONSDATA* consdata;
2319
2320 assert(scip != NULL);
2321
2322 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2323 {
2324 SCIPerrorMessage("constraint is not an or constraint\n");
2325 SCIPABORT();
2326 return NULL; /*lint !e527*/
2327 }
2328
2329 consdata = SCIPconsGetData(cons);
2330 assert(consdata != NULL);
2331
2332 return consdata->vars;
2333}
2334
2335/** gets the resultant variable in or constraint */
2337 SCIP* scip, /**< SCIP data structure */
2338 SCIP_CONS* cons /**< constraint data */
2339 )
2340{
2341 SCIP_CONSDATA* consdata;
2342
2343 assert(scip != NULL);
2344
2345 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2346 {
2347 SCIPerrorMessage("constraint is not a or constraint\n");
2348 SCIPABORT();
2349 return NULL; /*lint !e527*/
2350 }
2351
2352 consdata = SCIPconsGetData(cons);
2353 assert(consdata != NULL);
2354
2355 return consdata->resvar;
2356}
SCIP_Real * r
Definition: circlepacking.c:59
enum Proprule PROPRULE
Definition: cons_and.c:179
Proprule
Definition: cons_and.c:172
Constraint handler for AND constraints, .
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
Definition: cons_or.c:749
enum Proprule PROPRULE
Definition: cons_or.c:137
static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA *consdata)
Definition: cons_or.c:449
static SCIP_DECL_CONSFREE(consFreeOr)
Definition: cons_or.c:1489
static int consdataGetNRows(SCIP_CONSDATA *consdata)
Definition: cons_or.c:211
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
Definition: cons_or.c:510
static SCIP_RETCODE consdataCatchWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int *filterpos)
Definition: cons_or.c:222
static SCIP_RETCODE consdataDropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_or.c:295
static SCIP_RETCODE consdataSwitchWatchedvars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_or.c:321
#define CONSHDLR_NEEDSCONS
Definition: cons_or.c:86
#define CONSHDLR_SEPAFREQ
Definition: cons_or.c:79
static SCIP_DECL_CONSPARSE(consParseOr)
Definition: cons_or.c:1998
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_or.c:589
#define CONSHDLR_CHECKPRIORITY
Definition: cons_or.c:78
#define CONSHDLR_DESC
Definition: cons_or.c:75
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
Definition: cons_or.c:535
static SCIP_DECL_CONSENFOPS(consEnfopsOr)
Definition: cons_or.c:1703
static SCIP_DECL_CONSTRANS(consTransOr)
Definition: cons_or.c:1540
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:706
#define CONSHDLR_PROP_TIMING
Definition: cons_or.c:88
static SCIP_DECL_CONSGETNVARS(consGetNVarsOr)
Definition: cons_or.c:2098
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_or.c:198
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_or.c:162
#define CONSHDLR_MAXPREROUNDS
Definition: cons_or.c:83
static SCIP_DECL_CONSPRESOL(consPresolOr)
Definition: cons_or.c:1777
#define CONSHDLR_SEPAPRIORITY
Definition: cons_or.c:76
static SCIP_DECL_CONSLOCK(consLockOr)
Definition: cons_or.c:1907
static SCIP_RETCODE analyzeConflictOne(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:981
static SCIP_RETCODE analyzeConflictZero(SCIP *scip, SCIP_CONS *cons, int truepos)
Definition: cons_or.c:949
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
Definition: cons_or.c:1400
static SCIP_DECL_CONSSEPASOL(consSepasolOr)
Definition: cons_or.c:1611
static SCIP_DECL_CONSRESPROP(consRespropOr)
Definition: cons_or.c:1897
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_or.c:146
static SCIP_DECL_CONSSEPALP(consSepalpOr)
Definition: cons_or.c:1587
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num)
Definition: cons_or.c:381
@ PROPRULE_2
Definition: cons_or.c:132
@ PROPRULE_1
Definition: cons_or.c:131
@ PROPRULE_3
Definition: cons_or.c:133
@ PROPRULE_INVALID
Definition: cons_or.c:135
@ PROPRULE_4
Definition: cons_or.c:134
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated)
Definition: cons_or.c:783
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_or.c:476
static SCIP_DECL_CONSPRINT(consPrintOr)
Definition: cons_or.c:1932
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOr)
Definition: cons_or.c:1473
static SCIP_DECL_CONSGETVARS(consGetVarsOr)
Definition: cons_or.c:2077
static SCIP_DECL_CONSCHECK(consCheckOr)
Definition: cons_or.c:1725
static SCIP_RETCODE consdataDropWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int filterpos)
Definition: cons_or.c:246
static SCIP_DECL_CONSDELETE(consDeleteOr)
Definition: cons_or.c:1525
#define CONSHDLR_PROPFREQ
Definition: cons_or.c:80
static SCIP_RETCODE upgradeCons(SCIP *scip, SCIP_CONS *cons, int *nupgdconss)
Definition: cons_or.c:1347
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphOr)
Definition: cons_or.c:2124
#define CONSHDLR_PRESOLTIMING
Definition: cons_or.c:89
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_or.c:1022
static SCIP_DECL_CONSENFOLP(consEnfolpOr)
Definition: cons_or.c:1635
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphOr)
Definition: cons_or.c:2115
static SCIP_DECL_CONSPROP(consPropOr)
Definition: cons_or.c:1744
#define CONSHDLR_EAGERFREQ
Definition: cons_or.c:81
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated)
Definition: cons_or.c:899
#define EVENTHDLR_DESC
Definition: cons_or.c:92
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_or.c:178
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr, int nvars, SCIP_VAR **vars, SCIP_VAR *resvar)
Definition: cons_or.c:405
#define CONSHDLR_ENFOPRIORITY
Definition: cons_or.c:77
static SCIP_DECL_CONSINITLP(consInitlpOr)
Definition: cons_or.c:1569
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_or.c:647
static SCIP_DECL_EVENTEXEC(eventExecOr)
Definition: cons_or.c:2136
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
Definition: cons_or.c:1261
#define CONSHDLR_DELAYSEPA
Definition: cons_or.c:84
static SCIP_DECL_CONSCOPY(consCopyOr)
Definition: cons_or.c:1945
#define CONSHDLR_NAME
Definition: cons_or.c:74
#define EVENTHDLR_NAME
Definition: cons_or.c:91
static SCIP_DECL_CONSENFORELAX(consEnforelaxOr)
Definition: cons_or.c:1669
static SCIP_DECL_CONSEXITSOL(consExitsolOr)
Definition: cons_or.c:1507
#define CONSHDLR_DELAYPROP
Definition: cons_or.c:85
static SCIP_RETCODE consdataCatchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_or.c:269
Constraint handler for "or" constraints, .
#define NULL
Definition: def.h:266
#define SCIP_MAXSTRLEN
Definition: def.h:287
#define SCIP_Bool
Definition: def.h:91
#define MAX3(x, y, z)
Definition: def.h:246
#define SCIP_Real
Definition: def.h:172
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIPABORT()
Definition: def.h:345
#define SCIP_CALL(x)
Definition: def.h:373
SCIP_VAR ** SCIPgetVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2313
int SCIPgetNVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2290
SCIP_RETCODE SCIPcreateConsAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_and.c:5082
SCIP_RETCODE SCIPcreateConsBasicOr(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars)
Definition: cons_or.c:2274
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2336
SCIP_RETCODE SCIPcreateConsOr(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_or.c:2212
SCIP_RETCODE SCIPincludeConshdlrOr(SCIP *scip)
Definition: cons_or.c:2162
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:711
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:606
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:734
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:390
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 SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3475
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition: cons.c:4227
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:235
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETPERMSYMGRAPH((*consgetpermsymgraph)))
Definition: scip_cons.c:900
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH((*consgetsignedpermsymgraph)))
Definition: scip_cons.c:924
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITSOL((*consexitsol)))
Definition: scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8244
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8473
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8383
SCIP_RETCODE SCIPprintCons(SCIP *scip, SCIP_CONS *cons, FILE *file)
Definition: scip_cons.c:2537
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8343
SCIP_Bool SCIPconsIsTransformed(SCIP_CONS *cons)
Definition: cons.c:8523
SCIP_Bool SCIPconsIsLockedType(SCIP_CONS *cons, SCIP_LOCKTYPE locktype)
Definition: cons.c:8607
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:998
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8453
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_RETCODE SCIPresetConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1813
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8463
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8493
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition: scip_cons.c:1174
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition: scip_cons.c:1785
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8483
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPincludeEventhdlrBasic(SCIP *scip, SCIP_EVENTHDLR **eventhdlrptr, const char *name, const char *desc, SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: scip_event.c:111
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:361
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:407
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_RETCODE SCIPaddVarsToRowSameCoef(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real val)
Definition: scip_lp.c:1773
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1422
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition: scip_lp.c:2167
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17551
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:125
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1213
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:146
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4474
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17626
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1480
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8676
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18171
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17588
SCIP_RETCODE SCIPparseVarsList(SCIP *scip, const char *str, SCIP_VAR **vars, int *nvars, int varssize, int *requiredsize, char **endptr, char delimiter, SCIP_Bool *success)
Definition: scip_var.c:610
SCIP_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition: scip_var.c:8512
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:533
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18115
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4382
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4560
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17446
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition: scip_var.c:1527
SCIP_RETCODE SCIPaddVarImplication(SCIP *scip, SCIP_VAR *var, SCIP_Bool varfixing, SCIP_VAR *implvar, SCIP_BOUNDTYPE impltype, SCIP_Real implbound, SCIP_Bool *infeasible, int *nbdchgs)
Definition: scip_var.c:6903
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18161
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18105
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5846
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:230
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition: scip_var.c:1597
SCIP_RETCODE SCIPwriteVarsList(SCIP *scip, FILE *file, SCIP_VAR **vars, int nvars, SCIP_Bool type, char delimiter)
Definition: scip_var.c:292
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1439
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10880
char * SCIPstrtok(char *s, const char *delim, char **ptrptr)
Definition: misc.c:10821
SCIP_RETCODE SCIPaddSymgraphEdge(SCIP *scip, SYM_GRAPH *graph, int first, int second, SCIP_Bool hasval, SCIP_Real val)
SCIP_RETCODE SCIPaddSymgraphOpnode(SCIP *scip, SYM_GRAPH *graph, int op, int *nodeidx)
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPaddSymgraphConsnode(SCIP *scip, SYM_GRAPH *graph, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, int *nodeidx)
SCIP_RETCODE SCIPaddSymgraphVarAggregation(SCIP *scip, SYM_GRAPH *graph, int rootidx, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_Real constant)
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
public methods for managing constraints
public methods for managing events
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebug(x)
Definition: pub_message.h:93
public data structures and miscellaneous methods
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for the branch-and-bound tree
public methods for SCIP variables
structs for symmetry computations
methods for dealing with symmetry detection graphs
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition: type_event.h:125
struct SCIP_EventData SCIP_EVENTDATA
Definition: type_event.h:173
#define SCIP_EVENTTYPE_UBTIGHTENED
Definition: type_event.h:79
#define SCIP_EVENTTYPE_LBRELAXED
Definition: type_event.h:78
#define SCIP_EVENTTYPE_LBTIGHTENED
Definition: type_event.h:77
#define SCIP_EVENTTYPE_UBRELAXED
Definition: type_event.h:80
@ SCIP_BOUNDTYPE_UPPER
Definition: type_lp.h:57
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_INFEASIBLE
Definition: type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
@ SCIP_INVALIDCALL
Definition: type_retcode.h:51
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
@ SYM_CONSOPTYPE_OR
Definition: type_symmetry.h:93
@ SYM_SYMTYPE_SIGNPERM
Definition: type_symmetry.h:62
@ SYM_SYMTYPE_PERM
Definition: type_symmetry.h:61
@ SCIP_LOCKTYPE_CONFLICT
Definition: type_var.h:98
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97