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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file cons_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 = 0.0;
1413 int nlocvars;
1414 int nvars;
1415 int i;
1416
1417 assert(scip != NULL);
1418 assert(cons != NULL);
1419 assert(graph != NULL);
1420 assert(success != NULL);
1421
1422 consdata = SCIPconsGetData(cons);
1423 assert(consdata != NULL);
1424
1425 /* get active variables of the constraint */
1426 nvars = SCIPgetNVars(scip);
1427 nlocvars = SCIPgetNVarsOr(scip, cons);
1428
1429 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1430 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
1431
1432 orvars = SCIPgetVarsOr(scip, cons);
1433 for( i = 0; i < consdata->nvars; ++i )
1434 {
1435 vars[i] = orvars[i];
1436 vals[i] = 1.0;
1437 }
1438
1439 assert(SCIPgetResultantOr(scip, cons) != NULL);
1440 vars[nlocvars] = SCIPgetResultantOr(scip, cons);
1441 vals[nlocvars++] = 2.0;
1442 assert(nlocvars <= nvars);
1443
1444 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
1445
1446 /* represent the OR constraint via the gadget for linear constraints and use the constant as lhs/rhs to
1447 * distinguish different OR constraints (OR constraints do not have an intrinsic right-hand side)
1448 */
1449 SCIP_CALL( SCIPextendPermsymDetectionGraphLinear(scip, graph, vars, vals, nlocvars,
1450 cons, -constant, -constant, success) );
1451
1452 SCIPfreeBufferArray(scip, &vals);
1453 SCIPfreeBufferArray(scip, &vars);
1454
1455 return SCIP_OKAY;
1456}
1457
1458/*
1459 * Callback methods of constraint handler
1460 */
1461
1462/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1463static
1465{ /*lint --e{715}*/
1466 assert(scip != NULL);
1467 assert(conshdlr != NULL);
1468 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1469
1470 /* call inclusion method of constraint handler */
1472
1473 *valid = TRUE;
1474
1475 return SCIP_OKAY;
1476}
1477
1478/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
1479static
1481{ /*lint --e{715}*/
1482 SCIP_CONSHDLRDATA* conshdlrdata;
1483
1484 /* free constraint handler data */
1485 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1486 assert(conshdlrdata != NULL);
1487
1488 conshdlrdataFree(scip, &conshdlrdata);
1489
1490 SCIPconshdlrSetData(conshdlr, NULL);
1491
1492 return SCIP_OKAY;
1493}
1494
1495
1496/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
1497static
1499{ /*lint --e{715}*/
1500 SCIP_CONSDATA* consdata;
1501 int c;
1502
1503 /* release and free the rows of all constraints */
1504 for( c = 0; c < nconss; ++c )
1505 {
1506 consdata = SCIPconsGetData(conss[c]);
1507 SCIP_CALL( consdataFreeRows(scip, consdata) );
1508 }
1509
1510 return SCIP_OKAY;
1511}
1512
1513
1514/** frees specific constraint data */
1515static
1517{ /*lint --e{715}*/
1518 SCIP_CONSHDLRDATA* conshdlrdata;
1519
1520 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1521 assert(conshdlrdata != NULL);
1522
1523 SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
1524
1525 return SCIP_OKAY;
1526}
1527
1528
1529/** transforms constraint data into data belonging to the transformed problem */
1530static
1532{ /*lint --e{715}*/
1533 SCIP_CONSHDLRDATA* conshdlrdata;
1534 SCIP_CONSDATA* sourcedata;
1535 SCIP_CONSDATA* targetdata;
1536
1537 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1538 assert(conshdlrdata != NULL);
1539
1540 sourcedata = SCIPconsGetData(sourcecons);
1541 assert(sourcedata != NULL);
1542
1543 /* create target constraint data */
1544 SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
1545 sourcedata->nvars, sourcedata->vars, sourcedata->resvar) );
1546
1547 /* create target constraint */
1548 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1549 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1550 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
1551 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
1552 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1553
1554 return SCIP_OKAY;
1555}
1556
1557
1558/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1559static
1561{ /*lint --e{715}*/
1562 int i;
1563
1564 *infeasible = FALSE;
1565
1566 for( i = 0; i < nconss && !(*infeasible); i++ )
1567 {
1568 assert(SCIPconsIsInitial(conss[i]));
1569 SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
1570 }
1571
1572 return SCIP_OKAY;
1573}
1574
1575
1576/** separation method of constraint handler for LP solutions */
1577static
1579{ /*lint --e{715}*/
1580 SCIP_Bool separated;
1581 int c;
1582
1583 *result = SCIP_DIDNOTFIND;
1584
1585 /* separate all useful constraints */
1586 for( c = 0; c < nusefulconss; ++c )
1587 {
1588 SCIP_CALL( separateCons(scip, conss[c], NULL, &separated) );
1589 if( separated )
1590 *result = SCIP_SEPARATED;
1591 }
1592
1593 /* combine constraints to get more cuts */
1594 /**@todo combine constraints to get further cuts */
1595
1596 return SCIP_OKAY;
1597}
1598
1599
1600/** separation method of constraint handler for arbitrary primal solutions */
1601static
1603{ /*lint --e{715}*/
1604 SCIP_Bool separated;
1605 int c;
1606
1607 *result = SCIP_DIDNOTFIND;
1608
1609 /* separate all useful constraints */
1610 for( c = 0; c < nusefulconss; ++c )
1611 {
1612 SCIP_CALL( separateCons(scip, conss[c], sol, &separated) );
1613 if( separated )
1614 *result = SCIP_SEPARATED;
1615 }
1616
1617 /* combine constraints to get more cuts */
1618 /**@todo combine constraints to get further cuts */
1619
1620 return SCIP_OKAY;
1621}
1622
1623
1624/** constraint enforcing method of constraint handler for LP solutions */
1625static
1627{ /*lint --e{715}*/
1628 SCIP_Bool violated;
1629 int i;
1630
1631 /* method is called only for integral solutions, because the enforcing priority is negative */
1632 for( i = 0; i < nconss; i++ )
1633 {
1634 SCIP_CALL( checkCons(scip, conss[i], NULL, FALSE, FALSE, &violated) );
1635 if( violated )
1636 {
1637 SCIP_Bool separated;
1638
1639 SCIP_CALL( separateCons(scip, conss[i], NULL, &separated) );
1640
1641 /* if the solution is integral, the separation always finds a cut
1642 * if some implicit binary variable is not integral, then some other constraint needs to be enforced first
1643 */
1644 if( separated )
1645 *result = SCIP_SEPARATED;
1646 else
1647 *result = SCIP_INFEASIBLE;
1648
1649 return SCIP_OKAY;
1650 }
1651 }
1652 *result = SCIP_FEASIBLE;
1653
1654 return SCIP_OKAY;
1655}
1656
1657
1658/** constraint enforcing method of constraint handler for relaxation solutions */
1659static
1661{ /*lint --e{715}*/
1662 SCIP_Bool violated;
1663 int i;
1664
1665 /* method is called only for integral solutions, because the enforcing priority is negative */
1666 for( i = 0; i < nconss; i++ )
1667 {
1668 SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
1669 if( violated )
1670 {
1671 SCIP_Bool separated;
1672
1673 SCIP_CALL( separateCons(scip, conss[i], sol, &separated) );
1674
1675 /* if the solution is integral, the separation always finds a cut
1676 * if some implicit binary variable is not integral, then some other constraint needs to be enforced first
1677 */
1678 if( separated )
1679 *result = SCIP_SEPARATED;
1680 else
1681 *result = SCIP_INFEASIBLE;
1682
1683 return SCIP_OKAY;
1684 }
1685 }
1686 *result = SCIP_FEASIBLE;
1687
1688 return SCIP_OKAY;
1689}
1690
1691
1692/** constraint enforcing method of constraint handler for pseudo solutions */
1693static
1695{ /*lint --e{715}*/
1696 SCIP_Bool violated;
1697 int i;
1698
1699 /* method is called only for integral solutions, because the enforcing priority is negative */
1700 for( i = 0; i < nconss; i++ )
1701 {
1702 SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
1703 if( violated )
1704 {
1705 *result = SCIP_INFEASIBLE;
1706 return SCIP_OKAY;
1707 }
1708 }
1709 *result = SCIP_FEASIBLE;
1710
1711 return SCIP_OKAY;
1712}
1713
1714/** feasibility check method of constraint handler or */
1715static
1717{ /*lint --e{715}*/
1718 SCIP_Bool violated;
1719 int i;
1720
1721 *result = SCIP_FEASIBLE;
1722
1723 for( i = 0; i < nconss && ( *result == SCIP_FEASIBLE || completely ); ++i )
1724 {
1725 SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
1726 if( violated )
1727 *result = SCIP_INFEASIBLE;
1728 }
1729
1730 return SCIP_OKAY;
1731}
1732
1733/** domain propagation method of constraint handler */
1734static
1736{ /*lint --e{715}*/
1737 SCIP_CONSHDLRDATA* conshdlrdata;
1738 SCIP_Bool cutoff;
1739 int nfixedvars;
1740 int c;
1741
1742 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1743 assert(conshdlrdata != NULL);
1744
1745 cutoff = FALSE;
1746 nfixedvars = 0;
1747
1748 /* propagate all useful constraints */
1749 for( c = 0; c < nusefulconss && !cutoff; ++c )
1750 {
1751 SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars) );
1752 }
1753
1754 /* return the correct result */
1755 if( cutoff )
1756 *result = SCIP_CUTOFF;
1757 else if( nfixedvars > 0 )
1758 *result = SCIP_REDUCEDDOM;
1759 else
1760 *result = SCIP_DIDNOTFIND;
1761
1762 return SCIP_OKAY;
1763}
1764
1765
1766/** presolving method of constraint handler */
1767static
1769{ /*lint --e{715}*/
1770 SCIP_CONSHDLRDATA* conshdlrdata;
1771 SCIP_CONS* cons;
1772 SCIP_CONSDATA* consdata;
1773 SCIP_Bool cutoff;
1774 SCIP_Bool redundant;
1775 SCIP_Bool aggregated;
1776 int oldnfixedvars;
1777 int oldnaggrvars;
1778 int oldnupgdconss;
1779 int c;
1780
1781 assert(result != NULL);
1782
1783 *result = SCIP_DIDNOTFIND;
1784 oldnfixedvars = *nfixedvars;
1785 oldnaggrvars = *naggrvars;
1786 oldnupgdconss = *nupgdconss;
1787
1788 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1789 assert(conshdlrdata != NULL);
1790
1791 /* process constraints */
1792 cutoff = FALSE;
1793 for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
1794 {
1795 cons = conss[c];
1796 assert(cons != NULL);
1797 consdata = SCIPconsGetData(cons);
1798 assert(consdata != NULL);
1799
1800 /* force presolving the constraint in the initial round */
1801 if( nrounds == 0 )
1802 consdata->propagated = FALSE;
1803
1804 /* propagate constraint */
1805 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars) );
1806
1807 /* remove all variables that are fixed to one */
1808 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr) );
1809
1810 /* transform or constraints into and constraints on the negated variables in order to improve
1811 * the pairwise constraint presolving possibilities
1812 */
1813 SCIP_CALL( upgradeCons(scip, cons, nupgdconss) );
1814
1815 if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
1816 {
1817 assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
1818
1819 /* if only one variable is left, the resultant has to be equal to this single variable */
1820 if( consdata->nvars == 1 )
1821 {
1822 SCIPdebugMsg(scip, "or constraint <%s> has only one variable not fixed to 0.0\n", SCIPconsGetName(cons));
1823
1824 assert(consdata->vars != NULL);
1825 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
1826 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
1827
1828 /* aggregate variables: resultant - operand == 0 */
1829 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
1830 &cutoff, &redundant, &aggregated) );
1831 assert(redundant || SCIPdoNotAggr(scip));
1832
1833 if( aggregated )
1834 {
1835 assert(redundant);
1836 (*naggrvars)++;
1837 }
1838
1839 if( redundant )
1840 {
1841 /* delete constraint */
1842 SCIP_CALL( SCIPdelCons(scip, cons) );
1843 (*ndelconss)++;
1844 }
1845 }
1846 else if( !consdata->impladded )
1847 {
1848 int i;
1849
1850 /* add implications: resultant == 0 -> all operands == 0 */
1851 for( i = 0; i < consdata->nvars && !cutoff; ++i )
1852 {
1853 int nimplbdchgs;
1854
1855 SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, FALSE, consdata->vars[i],
1856 SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
1857 *nchgbds += nimplbdchgs;
1858 }
1859 consdata->impladded = TRUE;
1860 }
1861
1862 /* if in r = x or y, the resultant is fixed to one, add implication x = 0 -> y = 1 */
1863 if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
1864 && SCIPvarGetLbGlobal(consdata->resvar) > 0.5 )
1865 {
1866 int nimplbdchgs;
1867
1868 SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], FALSE, consdata->vars[1],
1869 SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
1870 (*nchgbds) += nimplbdchgs;
1871 consdata->opimpladded = TRUE;
1872 }
1873 }
1874 }
1875
1876 /* return the correct result code */
1877 if( cutoff )
1878 *result = SCIP_CUTOFF;
1879 else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nupgdconss > oldnupgdconss )
1880 *result = SCIP_SUCCESS;
1881
1882 return SCIP_OKAY;
1883}
1884
1885
1886/** propagation conflict resolving method of constraint handler */
1887static
1889{ /*lint --e{715}*/
1890 SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
1891
1892 return SCIP_OKAY;
1893}
1894
1895
1896/** variable rounding lock method of constraint handler */
1897static
1899{ /*lint --e{715}*/
1900 SCIP_CONSDATA* consdata;
1901 int i;
1902
1903 assert(locktype == SCIP_LOCKTYPE_MODEL);
1904
1905 consdata = SCIPconsGetData(cons);
1906 assert(consdata != NULL);
1907
1908 /* lock resultant variable */
1909 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->resvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
1910
1911 /* lock all operand variables */
1912 for( i = 0; i < consdata->nvars; ++i )
1913 {
1914 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
1915 }
1916
1917 return SCIP_OKAY;
1918}
1919
1920
1921/** constraint display method of constraint handler */
1922static
1924{ /*lint --e{715}*/
1925 assert( scip != NULL );
1926 assert( conshdlr != NULL );
1927 assert( cons != NULL );
1928
1930
1931 return SCIP_OKAY;
1932}
1933
1934/** constraint copying method of constraint handler */
1935static
1937{ /*lint --e{715}*/
1938 SCIP_VAR** sourcevars;
1939 SCIP_VAR** vars;
1940 SCIP_VAR* sourceresvar;
1941 SCIP_VAR* resvar;
1942 int nvars;
1943 int v;
1944
1945 assert(valid != NULL);
1946 (*valid) = TRUE;
1947 resvar = NULL;
1948
1949 /* get variables that need to be copied */
1950 sourceresvar = SCIPgetResultantOr(sourcescip, sourcecons);
1951 sourcevars = SCIPgetVarsOr(sourcescip, sourcecons);
1952 nvars = SCIPgetNVarsOr(sourcescip, sourcecons);
1953
1954 if( nvars == -1 )
1955 return SCIP_INVALIDCALL;
1956
1957 /* allocate buffer array */
1958 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1959
1960 /* map operand variables to active variables of the target SCIP */
1961 for( v = 0; v < nvars && *valid; ++v )
1962 {
1963 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
1964 assert(!(*valid) || vars[v] != NULL);
1965 }
1966
1967 /* map resultant to active variable of the target SCIP */
1968 if( *valid )
1969 {
1970 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
1971 assert(!(*valid) || resvar != NULL);
1972
1973 if( *valid )
1974 {
1975 assert(resvar != NULL);
1976 SCIP_CALL( SCIPcreateConsOr(scip, cons, SCIPconsGetName(sourcecons), resvar, nvars, vars,
1977 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1978 }
1979 }
1980
1981 /* free buffer array */
1982 SCIPfreeBufferArray(scip, &vars);
1983
1984 return SCIP_OKAY;
1985}
1986
1987/** constraint parsing method of constraint handler */
1988static
1990{ /*lint --e{715}*/
1991 SCIP_VAR** vars;
1992 SCIP_VAR* resvar;
1993 char* strcopy;
1994 char* token;
1995 char* saveptr;
1996 char* endptr;
1997 int requiredsize;
1998 int varssize;
1999 int nvars;
2000
2001 SCIPdebugMsg(scip, "parse <%s> as or constraint\n", str);
2002
2003 *success = FALSE;
2004
2005 /* copy string for truncating it */
2006 SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, str, (int)(strlen(str)+1)));
2007
2008 /* cutoff "or" form the constraint string */
2009 token = SCIPstrtok(strcopy, "=", &saveptr );
2010
2011 /* parse variable name */
2012 SCIP_CALL( SCIPparseVarName(scip, token, &resvar, &endptr) );
2013
2014 if( resvar == NULL )
2015 {
2016 SCIPerrorMessage("resultant variable does not exist\n");
2017 }
2018 else
2019 {
2020 /* cutoff "or" form the constraint string */
2021 (void) SCIPstrtok(NULL, "(", &saveptr );
2022
2023 /* cutoff ")" form the constraint string */
2024 token = SCIPstrtok(NULL, ")", &saveptr );
2025
2026 varssize = 100;
2027 nvars = 0;
2028
2029 /* allocate buffer array for variables */
2030 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
2031
2032 /* parse string */
2033 SCIP_CALL( SCIPparseVarsList(scip, token, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
2034
2035 if( *success )
2036 {
2037 /* check if the size of the variable array was great enough */
2038 if( varssize < requiredsize )
2039 {
2040 /* reallocate memory */
2041 varssize = requiredsize;
2042 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
2043
2044 /* parse string again with the correct size of the variable array */
2045 SCIP_CALL( SCIPparseVarsList(scip, token, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
2046 }
2047
2048 assert(*success);
2049 assert(varssize >= requiredsize);
2050
2051 /* create and constraint */
2052 SCIP_CALL( SCIPcreateConsOr(scip, cons, name, resvar, nvars, vars,
2053 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2054 }
2055
2056 /* free variable buffer */
2057 SCIPfreeBufferArray(scip, &vars);
2058 }
2059
2060 /* free string buffer */
2061 SCIPfreeBufferArray(scip, &strcopy);
2062
2063 return SCIP_OKAY;
2064}
2065
2066/** constraint method of constraint handler which returns the variables (if possible) */
2067static
2069{ /*lint --e{715}*/
2070 SCIP_CONSDATA* consdata;
2071
2072 consdata = SCIPconsGetData(cons);
2073 assert(consdata != NULL);
2074
2075 if( varssize < consdata->nvars + 1 )
2076 (*success) = FALSE;
2077 else
2078 {
2079 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
2080 vars[consdata->nvars] = consdata->resvar;
2081 (*success) = TRUE;
2082 }
2083
2084 return SCIP_OKAY;
2085}
2086
2087/** constraint method of constraint handler which returns the number of variable (if possible) */
2088static
2090{ /*lint --e{715}*/
2091 SCIP_CONSDATA* consdata;
2092
2093 assert(cons != NULL);
2094
2095 consdata = SCIPconsGetData(cons);
2096 assert(consdata != NULL);
2097
2098 (*nvars) = consdata->nvars + 1;
2099 (*success) = TRUE;
2100
2101 return SCIP_OKAY;
2102}
2103
2104/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
2105static
2106SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphOr)
2107{ /*lint --e{715}*/
2108 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) );
2109
2110 return SCIP_OKAY;
2111}
2112
2113/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
2114static
2115SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphOr)
2116{ /*lint --e{715}*/
2117 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) );
2118
2119 return SCIP_OKAY;
2120}
2121
2122/*
2123 * Callback methods of event handler
2124 */
2125
2126static
2128{ /*lint --e{715}*/
2129 SCIP_CONSDATA* consdata;
2130
2131 assert(eventhdlr != NULL);
2132 assert(eventdata != NULL);
2133 assert(event != NULL);
2134
2135 consdata = (SCIP_CONSDATA*)eventdata;
2136 assert(consdata != NULL);
2137
2138 /* check, if the variable was fixed to one */
2140 consdata->nofixedone = FALSE;
2141
2142 consdata->propagated = FALSE;
2143
2144 return SCIP_OKAY;
2145}
2146
2147
2148/*
2149 * constraint specific interface methods
2150 */
2151
2152/** creates the handler for or constraints and includes it in SCIP */
2154 SCIP* scip /**< SCIP data structure */
2155 )
2156{
2157 SCIP_CONSHDLRDATA* conshdlrdata;
2158 SCIP_CONSHDLR* conshdlr;
2159 SCIP_EVENTHDLR* eventhdlr;
2160
2161 /* create event handler for events on variables */
2163 eventExecOr, NULL) );
2164
2165 /* create constraint handler data */
2166 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
2167
2168 /* include constraint handler */
2171 consEnfolpOr, consEnfopsOr, consCheckOr, consLockOr,
2172 conshdlrdata) );
2173 assert(conshdlr != NULL);
2174
2175 /* set non-fundamental callbacks via specific setter functions */
2176 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOr, consCopyOr) );
2177 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOr) );
2178 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolOr) );
2179 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOr) );
2180 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOr) );
2181 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOr) );
2182 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOr) );
2183 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOr) );
2185 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOr) );
2188 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOr) );
2189 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOr, consSepasolOr, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY,
2191 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOr) );
2192 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOr) );
2193 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphOr) );
2194 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphOr) );
2195
2196 return SCIP_OKAY;
2197}
2198
2199/** creates and captures an or constraint
2200 *
2201 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2202 */
2204 SCIP* scip, /**< SCIP data structure */
2205 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2206 const char* name, /**< name of constraint */
2207 SCIP_VAR* resvar, /**< resultant variable of the operation */
2208 int nvars, /**< number of operator variables in the constraint */
2209 SCIP_VAR** vars, /**< array with operator variables of constraint */
2210 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2211 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2212 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2213 * Usually set to TRUE. */
2214 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2215 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2216 SCIP_Bool check, /**< should the constraint be checked for feasibility?
2217 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2218 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2219 * Usually set to TRUE. */
2220 SCIP_Bool local, /**< is constraint only valid locally?
2221 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2222 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2223 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2224 * adds coefficients to this constraint. */
2225 SCIP_Bool dynamic, /**< is constraint subject to aging?
2226 * Usually set to FALSE. Set to TRUE for own cuts which
2227 * are separated as constraints. */
2228 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2229 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2230 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2231 * if it may be moved to a more global node?
2232 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2233 )
2234{
2235 SCIP_CONSHDLR* conshdlr;
2236 SCIP_CONSHDLRDATA* conshdlrdata;
2237 SCIP_CONSDATA* consdata;
2238
2239 /* find the or constraint handler */
2240 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2241 if( conshdlr == NULL )
2242 {
2243 SCIPerrorMessage("or constraint handler not found\n");
2244 return SCIP_PLUGINNOTFOUND;
2245 }
2246
2247 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2248 assert(conshdlrdata != NULL);
2249
2250 /* create constraint data */
2251 SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar) );
2252
2253 /* create constraint */
2254 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2255 local, modifiable, dynamic, removable, stickingatnode) );
2256
2257 return SCIP_OKAY;
2258}
2259
2260/** creates and captures an or constraint
2261 * in its most basic variant, i. e., with all constraint flags set to their default values
2262 *
2263 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2264 */
2266 SCIP* scip, /**< SCIP data structure */
2267 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2268 const char* name, /**< name of constraint */
2269 SCIP_VAR* resvar, /**< resultant variable of the operation */
2270 int nvars, /**< number of operator variables in the constraint */
2271 SCIP_VAR** vars /**< array with operator variables of constraint */
2272 )
2273{
2274 SCIP_CALL( SCIPcreateConsOr(scip, cons, name, resvar, nvars, vars, TRUE, TRUE, TRUE, TRUE, TRUE,
2275 FALSE, FALSE, FALSE, FALSE, FALSE) );
2276
2277 return SCIP_OKAY;
2278}
2279
2280/** gets number of variables in or constraint */
2282 SCIP* scip, /**< SCIP data structure */
2283 SCIP_CONS* cons /**< constraint data */
2284 )
2285{
2286 SCIP_CONSDATA* consdata;
2287
2288 assert(scip != NULL);
2289
2290 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2291 {
2292 SCIPerrorMessage("constraint is not an or constraint\n");
2293 SCIPABORT();
2294 return -1; /*lint !e527*/
2295 }
2296
2297 consdata = SCIPconsGetData(cons);
2298 assert(consdata != NULL);
2299
2300 return consdata->nvars;
2301}
2302
2303/** gets array of variables in or constraint */
2305 SCIP* scip, /**< SCIP data structure */
2306 SCIP_CONS* cons /**< constraint data */
2307 )
2308{
2309 SCIP_CONSDATA* consdata;
2310
2311 assert(scip != NULL);
2312
2313 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2314 {
2315 SCIPerrorMessage("constraint is not an or constraint\n");
2316 SCIPABORT();
2317 return NULL; /*lint !e527*/
2318 }
2319
2320 consdata = SCIPconsGetData(cons);
2321 assert(consdata != NULL);
2322
2323 return consdata->vars;
2324}
2325
2326/** gets the resultant variable in or constraint */
2328 SCIP* scip, /**< SCIP data structure */
2329 SCIP_CONS* cons /**< constraint data */
2330 )
2331{
2332 SCIP_CONSDATA* consdata;
2333
2334 assert(scip != NULL);
2335
2336 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
2337 {
2338 SCIPerrorMessage("constraint is not a or constraint\n");
2339 SCIPABORT();
2340 return NULL; /*lint !e527*/
2341 }
2342
2343 consdata = SCIPconsGetData(cons);
2344 assert(consdata != NULL);
2345
2346 return consdata->resvar;
2347}
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:1480
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:1989
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:1694
static SCIP_DECL_CONSTRANS(consTransOr)
Definition: cons_or.c:1531
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:2089
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:1768
#define CONSHDLR_SEPAPRIORITY
Definition: cons_or.c:76
static SCIP_DECL_CONSLOCK(consLockOr)
Definition: cons_or.c:1898
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:1602
static SCIP_DECL_CONSRESPROP(consRespropOr)
Definition: cons_or.c:1888
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:1578
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:1923
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOr)
Definition: cons_or.c:1464
static SCIP_DECL_CONSGETVARS(consGetVarsOr)
Definition: cons_or.c:2068
static SCIP_DECL_CONSCHECK(consCheckOr)
Definition: cons_or.c:1716
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:1516
#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:2115
#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:1626
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphOr)
Definition: cons_or.c:2106
static SCIP_DECL_CONSPROP(consPropOr)
Definition: cons_or.c:1735
#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:1560
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:2127
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:1936
#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:1660
static SCIP_DECL_CONSEXITSOL(consExitsolOr)
Definition: cons_or.c:1498
#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:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Bool
Definition: def.h:91
#define MAX3(x, y, z)
Definition: def.h:247
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIPABORT()
Definition: def.h:346
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_VAR ** SCIPgetVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2304
int SCIPgetNVarsOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2281
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:5070
SCIP_RETCODE SCIPcreateConsBasicOr(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars)
Definition: cons_or.c:2265
SCIP_VAR * SCIPgetResultantOr(SCIP *scip, SCIP_CONS *cons)
Definition: cons_or.c:2327
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:2203
SCIP_RETCODE SCIPincludeConshdlrOr(SCIP *scip)
Definition: cons_or.c:2153
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:711
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:596
SCIP_Bool SCIPisStopped(SCIP *scip)
Definition: scip_general.c:724
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2770
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
SCIP_RETCODE SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:3474
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:104
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_RETCODE SCIPcatchVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:354
SCIP_RETCODE SCIPdropVarEvent(SCIP *scip, SCIP_VAR *var, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:400
#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:17523
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition: scip_sol.c:129
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPgetSymActiveVariables(SCIP *scip, SYM_SYMTYPE symtype, SCIP_VAR ***vars, SCIP_Real **scalars, int *nvars, SCIP_Real *constant, SCIP_Bool transformed)
SCIP_RETCODE SCIPextendPermsymDetectionGraphLinear(SCIP *scip, SYM_GRAPH *graph, SCIP_VAR **vars, SCIP_Real *vals, int nvars, SCIP_CONS *cons, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool *success)
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:4351
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
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:8565
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Bool SCIPvarIsTransformed(SCIP_VAR *var)
Definition: var.c:17561
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:8401
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:18088
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4437
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:17419
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:6780
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5723
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:230
SCIP_RETCODE 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:10877
char * SCIPstrtok(char *s, const char *delim, char **ptrptr)
Definition: misc.c:10818
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_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