Scippy

SCIP

Solving Constraint Integer Programs

cons_and.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_and.c
26 * @ingroup DEFPLUGINS_CONS
27 * @ingroup CONSHDLRS
28 * @brief Constraint handler for AND-constraints, \f$r = x_1 \wedge x_2 \wedge \dots \wedge x_n\f$
29 * @author Tobias Achterberg
30 * @author Stefan Heinz
31 * @author Michael Winkler
32 *
33 * This constraint handler deals with AND-constraints. These are constraint of the form:
34 *
35 * \f[
36 * r = x_1 \wedge x_2 \wedge \dots \wedge x_n
37 * \f]
38 *
39 * 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
40 * called resultant and the \f$x\f$'s operators.
41 */
42
43/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
44
46#include "scip/cons_and.h"
47#include "scip/cons_linear.h"
48#include "scip/cons_logicor.h"
50#include "scip/cons_setppc.h"
51#include "scip/expr_product.h"
52#include "scip/expr_var.h"
53#include "scip/debug.h"
54#include "scip/pub_cons.h"
55#include "scip/pub_event.h"
56#include "scip/pub_lp.h"
57#include "scip/pub_message.h"
58#include "scip/pub_misc.h"
59#include "scip/pub_misc_sort.h"
60#include "scip/pub_var.h"
61#include "scip/scip_conflict.h"
62#include "scip/scip_cons.h"
63#include "scip/scip_copy.h"
64#include "scip/scip_cut.h"
65#include "scip/scip_event.h"
66#include "scip/scip_expr.h"
67#include "scip/scip_general.h"
68#include "scip/scip_lp.h"
69#include "scip/scip_mem.h"
70#include "scip/scip_message.h"
71#include "scip/scip_nlp.h"
72#include "scip/scip_numerics.h"
73#include "scip/scip_param.h"
74#include "scip/scip_prob.h"
75#include "scip/scip_probing.h"
76#include "scip/scip_sol.h"
77#include "scip/scip_tree.h"
78#include "scip/scip_var.h"
79#include "scip/symmetry_graph.h"
81#include <string.h>
82
83
84/* constraint handler properties */
85#define CONSHDLR_NAME "and"
86#define CONSHDLR_DESC "constraint handler for AND-constraints: r = and(x1, ..., xn)"
87#define CONSHDLR_SEPAPRIORITY +850100 /**< priority of the constraint handler for separation */
88#define CONSHDLR_ENFOPRIORITY -850100 /**< priority of the constraint handler for constraint enforcing */
89#define CONSHDLR_CHECKPRIORITY -850100 /**< priority of the constraint handler for checking feasibility */
90#define CONSHDLR_SEPAFREQ 1 /**< frequency for separating cuts; zero means to separate only in the root node */
91#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
92#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
93 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
94#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
95#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
96#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
97#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
98
99#define CONSHDLR_PRESOLTIMING (SCIP_PRESOLTIMING_FAST | SCIP_PRESOLTIMING_EXHAUSTIVE)
100#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
101
102#define EVENTHDLR_NAME "and"
103#define EVENTHDLR_DESC "bound change event handler for AND-constraints"
104
105#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
106#define DEFAULT_LINEARIZE FALSE /**< should constraint get linearized and removed? */
107#define DEFAULT_ENFORCECUTS TRUE /**< should cuts be separated during LP enforcing? */
108#define DEFAULT_AGGRLINEARIZATION FALSE /**< should an aggregated linearization be used? */
109#define DEFAULT_UPGRRESULTANT TRUE /**< should all binary resultant variables be upgraded to implicit binary variables */
110#define DEFAULT_DUALPRESOLVING TRUE /**< should dual presolving be performed? */
111
112#define HASHSIZE_ANDCONS 500 /**< minimal size of hash table in and constraint tables */
113#define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
114#define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
115#define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
116
117/* @todo maybe use event SCIP_EVENTTYPE_VARUNLOCKED to decide for another dual-presolving run on a constraint */
118
119/*
120 * Data structures
121 */
122
123/** constraint data for AND-constraints */
124struct SCIP_ConsData
125{
126 SCIP_VAR** vars; /**< variables in the AND-constraint */
127 SCIP_VAR* resvar; /**< resultant variable */
128 SCIP_ROW** rows; /**< rows for linear relaxation of AND-constraint */
129 SCIP_ROW* aggrrow; /**< aggregated row for linear relaxation of AND-constraint */
130 SCIP_NLROW* nlrow; /**< row for representation in nonlinear relaxation */
131 int nvars; /**< number of variables in AND-constraint */
132 int varssize; /**< size of vars array */
133 int nrows; /**< number of rows for linear relaxation of AND-constraint */
134 int watchedvar1; /**< position of first watched operator variable */
135 int watchedvar2; /**< position of second watched operator variable */
136 int filterpos1; /**< event filter position of first watched operator variable */
137 int filterpos2; /**< event filter position of second watched operator variable */
138 unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
139 unsigned int nofixedzero:1; /**< is none of the operator variables fixed to FALSE? */
140 unsigned int impladded:1; /**< were the implications of the constraint already added? */
141 unsigned int opimpladded:1; /**< was the implication for 2 operands with fixed resultant added? */
142 unsigned int sorted:1; /**< are the constraint's variables sorted? */
143 unsigned int changed:1; /**< was constraint changed since last pair preprocessing round? */
144 unsigned int merged:1; /**< are the constraint's equal variables already merged? */
145 unsigned int checkwhenupgr:1; /**< if AND-constraint is upgraded to an logicor constraint or the and-
146 * constraint is linearized, should the check flag be set to true, even
147 * if the AND-constraint has a check flag set to false? */
148 unsigned int notremovablewhenupgr:1;/**< if AND-constraint is upgraded to an logicor constraint or the and-
149 * constraint is linearized, should the removable flag be set to false,
150 * even if the AND-constraint has a removable flag set to true? */
151};
152
153/** constraint handler data */
154struct SCIP_ConshdlrData
155{
156 SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events on watched variables */
157 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
158 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance */
159 SCIP_Bool linearize; /**< should constraint get linearized and removed? */
160 SCIP_Bool enforcecuts; /**< should cuts be separated during LP enforcing? */
161 SCIP_Bool aggrlinearization; /**< should an aggregated linearization be used? */
162 SCIP_Bool upgrresultant; /**< upgrade binary resultant variable to an implicit binary variable */
163 SCIP_Bool dualpresolving; /**< should dual presolving be performed? */
164};
165
166
167/*
168 * Propagation rules
169 */
170
172{
173 PROPRULE_INVALID = 0, /**< propagation was applied without a specific propagation rule */
174 PROPRULE_1 = 1, /**< v_i = FALSE => r = FALSE */
175 PROPRULE_2 = 2, /**< r = TRUE => v_i = TRUE for all i */
176 PROPRULE_3 = 3, /**< v_i = TRUE for all i => r = TRUE */
177 PROPRULE_4 = 4 /**< r = FALSE, v_i = TRUE for all i except j => v_j = FALSE */
179typedef enum Proprule PROPRULE;
180
181
182/*
183 * Local methods
184 */
185
186/** installs rounding locks for the given variable in the given AND-constraint */
187static
189 SCIP* scip, /**< SCIP data structure */
190 SCIP_CONS* cons, /**< constraint data */
191 SCIP_VAR* var /**< variable of constraint entry */
192 )
193{
194 /* rounding in both directions may violate the constraint */
195 SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
196
197 return SCIP_OKAY;
198}
199
200/** removes rounding locks for the given variable in the given AND-constraint */
201static
203 SCIP* scip, /**< SCIP data structure */
204 SCIP_CONS* cons, /**< constraint data */
205 SCIP_VAR* var /**< variable of constraint entry */
206 )
207{
208 /* rounding in both directions may violate the constraint */
209 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
210
211 return SCIP_OKAY;
212}
213
214/** creates constraint handler data */
215static
217 SCIP* scip, /**< SCIP data structure */
218 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
219 SCIP_EVENTHDLR* eventhdlr /**< event handler */
220 )
221{
222 assert(scip != NULL);
223 assert(conshdlrdata != NULL);
224 assert(eventhdlr != NULL);
225
226 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
227
228 /* set event handler for catching bound change events on variables */
229 (*conshdlrdata)->eventhdlr = eventhdlr;
230
231 return SCIP_OKAY;
232}
233
234/** frees constraint handler data */
235static
237 SCIP* scip, /**< SCIP data structure */
238 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
239 )
240{
241 assert(conshdlrdata != NULL);
242 assert(*conshdlrdata != NULL);
243
244 SCIPfreeBlockMemory(scip, conshdlrdata);
245}
246
247/** catches events for the watched variable at given position */
248static
250 SCIP* scip, /**< SCIP data structure */
251 SCIP_CONSDATA* consdata, /**< AND-constraint data */
252 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
253 int pos, /**< array position of variable to catch bound change events for */
254 int* filterpos /**< pointer to store position of event filter entry */
255 )
256{
257 assert(consdata != NULL);
258 assert(consdata->vars != NULL);
259 assert(eventhdlr != NULL);
260 assert(0 <= pos && pos < consdata->nvars);
261 assert(filterpos != NULL);
262
263 /* catch tightening events for lower bound and relaxed events for upper bounds on watched variable */
265 eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
266
267 return SCIP_OKAY;
268}
269
270
271/** drops events for the watched variable at given position */
272static
274 SCIP* scip, /**< SCIP data structure */
275 SCIP_CONSDATA* consdata, /**< AND-constraint data */
276 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
277 int pos, /**< array position of watched variable to drop bound change events for */
278 int filterpos /**< position of event filter entry */
279 )
280{
281 assert(consdata != NULL);
282 assert(consdata->vars != NULL);
283 assert(eventhdlr != NULL);
284 assert(0 <= pos && pos < consdata->nvars);
285 assert(filterpos >= 0);
286
287 /* drop tightening events for lower bound and relaxed events for upper bounds on watched variable */
289 eventhdlr, (SCIP_EVENTDATA*)consdata, filterpos) );
290
291 return SCIP_OKAY;
292}
293
294/** catches needed events on all variables of constraint, except the special ones for watched variables */
295static
297 SCIP* scip, /**< SCIP data structure */
298 SCIP_CONSDATA* consdata, /**< AND-constraint data */
299 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
300 )
301{
302 int i;
303
304 assert(consdata != NULL);
305
306 /* catch bound change events for both bounds on resultant variable */
308 eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
309
310 /* catch tightening events for upper bound and relaxed events for lower bounds on operator variables */
311 for( i = 0; i < consdata->nvars; ++i )
312 {
314 eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
315 }
316
317 return SCIP_OKAY;
318}
319
320/** drops events on all variables of constraint, except the special ones for watched variables */
321static
323 SCIP* scip, /**< SCIP data structure */
324 SCIP_CONSDATA* consdata, /**< AND-constraint data */
325 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
326 )
327{
328 int i;
329
330 assert(consdata != NULL);
331
332 /* drop bound change events for both bounds on resultant variable */
334 eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
335
336 /* drop tightening events for upper bound and relaxed events for lower bounds on operator variables */
337 for( i = 0; i < consdata->nvars; ++i )
338 {
340 eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
341 }
342
343 return SCIP_OKAY;
344}
345
346/** stores the given variable numbers as watched variables, and updates the event processing */
347static
349 SCIP* scip, /**< SCIP data structure */
350 SCIP_CONSDATA* consdata, /**< AND-constraint data */
351 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
352 int watchedvar1, /**< new first watched variable */
353 int watchedvar2 /**< new second watched variable */
354 )
355{
356 assert(consdata != NULL);
357 assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
358 assert(watchedvar1 != -1 || watchedvar2 == -1);
359 assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
360 assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
361
362 /* if one watched variable is equal to the old other watched variable, just switch positions */
363 if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
364 {
365 int tmp;
366
367 tmp = consdata->watchedvar1;
368 consdata->watchedvar1 = consdata->watchedvar2;
369 consdata->watchedvar2 = tmp;
370 tmp = consdata->filterpos1;
371 consdata->filterpos1 = consdata->filterpos2;
372 consdata->filterpos2 = tmp;
373 }
374 assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
375 assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
376
377 /* drop events on old watched variables */
378 if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
379 {
380 assert(consdata->filterpos1 != -1);
381 SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
382 }
383 if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
384 {
385 assert(consdata->filterpos2 != -1);
386 SCIP_CALL( consdataDropWatchedEvents(scip, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
387 }
388
389 /* catch events on new watched variables */
390 if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
391 {
392 SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) );
393 }
394 if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
395 {
396 SCIP_CALL( consdataCatchWatchedEvents(scip, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) );
397 }
398
399 /* set the new watched variables */
400 consdata->watchedvar1 = watchedvar1;
401 consdata->watchedvar2 = watchedvar2;
402
403 return SCIP_OKAY;
404}
405
406/** ensures, that the vars array can store at least num entries */
407static
409 SCIP* scip, /**< SCIP data structure */
410 SCIP_CONSDATA* consdata, /**< linear constraint data */
411 int num /**< minimum number of entries to store */
412 )
413{
414 assert(consdata != NULL);
415 assert(consdata->nvars <= consdata->varssize);
416
417 if( num > consdata->varssize )
418 {
419 int newsize;
420
421 newsize = SCIPcalcMemGrowSize(scip, num);
422 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
423 consdata->varssize = newsize;
424 }
425 assert(num <= consdata->varssize);
426
427 return SCIP_OKAY;
428}
429
430/** creates constraint data for AND-constraint */
431static
433 SCIP* scip, /**< SCIP data structure */
434 SCIP_CONSDATA** consdata, /**< pointer to store the constraint data */
435 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
436 int nvars, /**< number of variables in the AND-constraint */
437 SCIP_VAR** vars, /**< variables in AND-constraint */
438 SCIP_VAR* resvar, /**< resultant variable */
439 SCIP_Bool checkwhenupgr, /**< should an upgraded constraint be checked despite the fact that this
440 * AND-constraint will not be checked
441 */
442 SCIP_Bool notremovablewhenupgr/**< should an upgraded constraint be despite the fact that this
443 * AND-constraint will not be checked
444 */
445 )
446{
447 int v;
448
449 assert(consdata != NULL);
450 assert(nvars == 0 || vars != NULL);
451 assert(resvar != NULL);
452
453 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
454 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
455 (*consdata)->resvar = resvar;
456 (*consdata)->rows = NULL;
457 (*consdata)->aggrrow = NULL;
458 (*consdata)->nlrow = NULL;
459 (*consdata)->nvars = nvars;
460 (*consdata)->varssize = nvars;
461 (*consdata)->nrows = 0;
462 (*consdata)->watchedvar1 = -1;
463 (*consdata)->watchedvar2 = -1;
464 (*consdata)->filterpos1 = -1;
465 (*consdata)->filterpos2 = -1;
466 (*consdata)->propagated = FALSE;
467 (*consdata)->nofixedzero = FALSE;
468 (*consdata)->impladded = FALSE;
469 (*consdata)->opimpladded = FALSE;
470 (*consdata)->sorted = FALSE;
471 (*consdata)->changed = TRUE;
472 (*consdata)->merged = FALSE;
473 (*consdata)->checkwhenupgr = checkwhenupgr;
474 (*consdata)->notremovablewhenupgr = notremovablewhenupgr;
475
476 /* get transformed variables, if we are in the transformed problem */
478 {
479 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
480 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->resvar, &(*consdata)->resvar) );
481
482 /* catch needed events on variables */
483 SCIP_CALL( consdataCatchEvents(scip, *consdata, eventhdlr) );
484 }
485
486 assert(SCIPvarIsBinary((*consdata)->resvar));
487
488 /* note: currently, this constraint handler does not handle multiaggregations (e.g. during propagation), hence we forbid
489 * multiaggregation from the beginning for the involved variables
490 */
492 {
493 for( v = 0; v < (*consdata)->nvars; ++v )
494 {
495 assert((*consdata)->vars[v] != NULL);
496 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[v]) );
497 }
498 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->resvar) );
499 }
500
501 /* capture vars */
502 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->resvar) );
503 for( v = 0; v < (*consdata)->nvars; v++ )
504 {
505 assert((*consdata)->vars[v] != NULL);
506 assert(SCIPvarIsBinary((*consdata)->vars[v]));
507 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[v]) );
508 }
509
510 return SCIP_OKAY;
511}
512
513/** releases LP rows of constraint data and frees rows array */
514static
516 SCIP* scip, /**< SCIP data structure */
517 SCIP_CONSDATA* consdata /**< constraint data */
518 )
519{
520 int r;
521
522 assert(consdata != NULL);
523
524 if( consdata->rows != NULL )
525 {
526 for( r = 0; r < consdata->nrows; ++r )
527 {
528 SCIP_CALL( SCIPreleaseRow(scip, &consdata->rows[r]) );
529 }
530 SCIPfreeBlockMemoryArray(scip, &consdata->rows, consdata->nrows);
531
532 consdata->nrows = 0;
533 }
534
535 if( consdata->aggrrow != NULL )
536 {
537 SCIP_CALL( SCIPreleaseRow(scip, &consdata->aggrrow) );
538 consdata->aggrrow = NULL;
539 }
540
541 return SCIP_OKAY;
542}
543
544/** frees constraint data for AND-constraint */
545static
547 SCIP* scip, /**< SCIP data structure */
548 SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
549 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
550 )
551{
552 int v;
553
554 assert(consdata != NULL);
555 assert(*consdata != NULL);
556
558 {
559 /* drop events for watched variables */
560 SCIP_CALL( consdataSwitchWatchedvars(scip, *consdata, eventhdlr, -1, -1) );
561
562 /* drop all other events on variables */
563 SCIP_CALL( consdataDropEvents(scip, *consdata, eventhdlr) );
564 }
565 else
566 {
567 assert((*consdata)->watchedvar1 == -1);
568 assert((*consdata)->watchedvar2 == -1);
569 }
570
571 /* release and free the rows */
572 SCIP_CALL( consdataFreeRows(scip, *consdata) );
573
574 /* release the nlrow */
575 if( (*consdata)->nlrow != NULL )
576 {
577 SCIP_CALL( SCIPreleaseNlRow(scip, &(*consdata)->nlrow) );
578 }
579
580 /* release vars */
581 for( v = 0; v < (*consdata)->nvars; v++ )
582 {
583 assert((*consdata)->vars[v] != NULL);
584 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->vars[v])) );
585 }
586 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->resvar)) );
587
588 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
589 SCIPfreeBlockMemory(scip, consdata);
590
591 return SCIP_OKAY;
592}
593
594/** prints AND-constraint to file stream */
595static
597 SCIP* scip, /**< SCIP data structure */
598 SCIP_CONSDATA* consdata, /**< AND-constraint data */
599 FILE* file /**< output file (or NULL for standard output) */
600 )
601{
602 assert(consdata != NULL);
603
604 /* print resultant */
605 SCIP_CALL( SCIPwriteVarName(scip, file, consdata->resvar, TRUE) );
606
607 /* start the variable list */
608 SCIPinfoMessage(scip, file, " == and(");
609
610 /* print variable list */
611 SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
612
613 /* close the variable list */
614 SCIPinfoMessage(scip, file, ")");
615
616 return SCIP_OKAY;
617}
618
619/** adds coefficient to AND-constraint */
620static
622 SCIP* scip, /**< SCIP data structure */
623 SCIP_CONS* cons, /**< linear constraint */
624 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
625 SCIP_VAR* var /**< variable to add to the constraint */
626 )
627{
628 SCIP_CONSDATA* consdata;
629 SCIP_Bool transformed;
630
631 assert(var != NULL);
632
633 consdata = SCIPconsGetData(cons);
634 assert(consdata != NULL);
635 assert(consdata->rows == NULL);
636
637 /* are we in the transformed problem? */
638 transformed = SCIPconsIsTransformed(cons);
639
640 /* always use transformed variables in transformed constraints */
641 if( transformed )
642 {
643 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
644 }
645 assert(var != NULL);
646 assert(transformed == SCIPvarIsTransformed(var));
647
648 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
649 consdata->vars[consdata->nvars] = var;
650 consdata->nvars++;
651 consdata->sorted = (consdata->nvars == 1);
652 consdata->changed = TRUE;
653 consdata->merged = FALSE;
654
655 /* capture variable */
657
658 /* if we are in transformed problem, catch the variable's events */
659 if( transformed )
660 {
661 /* catch bound change events of variable */
663 eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
664 }
665
666 /* install the rounding locks for the new variable */
667 SCIP_CALL( lockRounding(scip, cons, var) );
668
669 /**@todo update LP rows */
670 if( consdata->rows != NULL )
671 {
672 SCIPerrorMessage("cannot add coefficients to AND-constraint after LP relaxation was created\n");
673 return SCIP_INVALIDCALL;
674 }
675
676 return SCIP_OKAY;
677}
678
679/** deletes coefficient at given position from AND-constraint data */
680static
682 SCIP* scip, /**< SCIP data structure */
683 SCIP_CONS* cons, /**< AND-constraint */
684 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
685 int pos /**< position of coefficient to delete */
686 )
687{
688 SCIP_CONSDATA* consdata;
689
690 assert(eventhdlr != NULL);
691
692 consdata = SCIPconsGetData(cons);
693 assert(consdata != NULL);
694 assert(0 <= pos && pos < consdata->nvars);
695 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
696
697 /* remove the rounding locks of the variable */
698 SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
699
700 if( SCIPconsIsTransformed(cons) )
701 {
702 /* drop bound change events of variable */
704 eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
705 }
706
707 if( SCIPconsIsTransformed(cons) )
708 {
709 /* if the position is watched, stop watching the position */
710 if( consdata->watchedvar1 == pos )
711 {
712 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar2, -1) );
713 }
714 if( consdata->watchedvar2 == pos )
715 {
716 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar1, -1) );
717 }
718 }
719 assert(pos != consdata->watchedvar1);
720 assert(pos != consdata->watchedvar2);
721
722 /* release variable */
723 SCIP_CALL( SCIPreleaseVar(scip, &(consdata->vars[pos])) );
724
725 /* move the last variable to the free slot */
726 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
727 consdata->nvars--;
728
729 /* if the last variable (that moved) was watched, update the watched position */
730 if( consdata->watchedvar1 == consdata->nvars )
731 consdata->watchedvar1 = pos;
732 if( consdata->watchedvar2 == consdata->nvars )
733 consdata->watchedvar2 = pos;
734
735 consdata->propagated = FALSE;
736 consdata->sorted = FALSE;
737 consdata->changed = TRUE;
738
739 return SCIP_OKAY;
740}
741
742/** sorts AND-constraint's variables by non-decreasing variable index */
743static
745 SCIP_CONSDATA* consdata /**< constraint data */
746 )
747{
748 assert(consdata != NULL);
749
750 if( !consdata->sorted )
751 {
752 if( consdata->nvars <= 1 )
753 consdata->sorted = TRUE;
754 else
755 {
756 SCIP_VAR* var1 = NULL;
757 SCIP_VAR* var2 = NULL;
758
759 /* remember watch variables */
760 if( consdata->watchedvar1 != -1 )
761 {
762 var1 = consdata->vars[consdata->watchedvar1];
763 assert(var1 != NULL);
764 consdata->watchedvar1 = -1;
765 if( consdata->watchedvar2 != -1 )
766 {
767 var2 = consdata->vars[consdata->watchedvar2];
768 assert(var2 != NULL);
769 consdata->watchedvar2 = -1;
770 }
771 }
772 assert(consdata->watchedvar1 == -1);
773 assert(consdata->watchedvar2 == -1);
774 assert(var1 != NULL || var2 == NULL);
775
776 /* sort variables after index */
777 SCIPsortPtr((void**)consdata->vars, SCIPvarComp, consdata->nvars);
778 consdata->sorted = TRUE;
779
780 /* correct watched variables */
781 if( var1 != NULL )
782 {
783 int pos;
784#ifndef NDEBUG
785 SCIP_Bool found;
786
787 found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var1, consdata->nvars, &pos);
788 assert(found);
789#else
790 (void) SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var1, consdata->nvars, &pos);
791#endif
792 assert(pos >= 0 && pos < consdata->nvars);
793 consdata->watchedvar1 = pos;
794
795 if( var2 != NULL )
796 {
797#ifndef NDEBUG
798 found = SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var2, consdata->nvars, &pos);
799 assert(found);
800#else
801 (void) SCIPsortedvecFindPtr((void**)consdata->vars, SCIPvarComp, (void*)var2, consdata->nvars, &pos);
802#endif
803 assert(pos >= 0 && pos < consdata->nvars);
804 consdata->watchedvar2 = pos;
805 }
806 }
807 }
808 }
809
810#ifdef SCIP_DEBUG
811 /* check sorting */
812 {
813 int v;
814
815 for( v = 0; v < consdata->nvars; ++v )
816 {
817 assert(v == consdata->nvars-1 || SCIPvarCompare(consdata->vars[v], consdata->vars[v+1]) <= 0);
818 }
819 }
820#endif
821}
822
823/** deletes all one-fixed variables */
824static
826 SCIP* scip, /**< SCIP data structure */
827 SCIP_CONS* cons, /**< AND-constraint */
828 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
829 int* nchgcoefs /**< pointer to add up the number of changed coefficients */
830 )
831{
832 SCIP_CONSDATA* consdata;
833 SCIP_VAR* var;
834 int v;
835
836 assert(scip != NULL);
837 assert(cons != NULL);
838 assert(eventhdlr != NULL);
839 assert(nchgcoefs != NULL);
840
841 consdata = SCIPconsGetData(cons);
842 assert(consdata != NULL);
843 assert(consdata->nvars == 0 || consdata->vars != NULL);
844
845 v = 0;
846 while( v < consdata->nvars )
847 {
848 var = consdata->vars[v];
849 assert(SCIPvarIsBinary(var));
850
851 if( SCIPvarGetLbGlobal(var) > 0.5 )
852 {
853 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), 1.0));
854 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
855 (*nchgcoefs)++;
856 }
857 else
858 {
859 SCIP_VAR* repvar;
860 SCIP_Bool negated;
861
862 /* get binary representative of variable */
863 SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
864
865 /* check, if the variable should be replaced with the representative */
866 if( repvar != var )
867 {
868 /* delete old (aggregated) variable */
869 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
870
871 /* add representative instead */
872 SCIP_CALL( addCoef(scip, cons, eventhdlr, repvar) );
873 }
874 else
875 ++v;
876 }
877 }
878
879#ifdef SCIP_DISABLED_CODE /* does not work with pseudoboolean constraint handler, need to be fixed */
880 /* check, if the resultant should be replaced with the active representative */
881 if( !SCIPvarIsActive(consdata->resvar) )
882 {
883 SCIP_VAR* repvar;
884 SCIP_Bool negated;
885
886 /* get binary representative of variable */
887 SCIP_CALL( SCIPgetBinvarRepresentative(scip, consdata->resvar, &repvar, &negated) );
888 assert(SCIPvarIsBinary(repvar));
889
890 /* check, if the variable should be replaced with the representative */
891 if( repvar != consdata->resvar )
892 {
893 if( SCIPconsIsTransformed(cons) )
894 {
895 /* drop bound change events of old resultant */
897 eventhdlr, (SCIP_EVENTDATA*)consdata, -1) );
898
899 /* catch bound change events of new resultant */
901 eventhdlr, (SCIP_EVENTDATA*)consdata, NULL) );
902 }
903
904 /* release old resultant */
905 SCIP_CALL( SCIPreleaseVar(scip, &(consdata->resvar)) );
906
907 /* capture new resultant */
908 SCIP_CALL( SCIPcaptureVar(scip, repvar) );
909
910 consdata->resvar = repvar;
911 consdata->changed = TRUE;
912 }
913 }
914#endif
915
916 SCIPdebugMsg(scip, "after fixings: ");
917 SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL)) );
918 SCIPdebugMsgPrint(scip, "\n");
919
920 return SCIP_OKAY;
921}
922
923/** creates a linearization of the AND-constraint */
924static
926 SCIP* scip, /**< SCIP data structure */
927 SCIP_CONS* cons /**< constraint to check */
928 )
929{
930 SCIP_CONSDATA* consdata;
931 char rowname[SCIP_MAXSTRLEN];
932 int nvars;
933 int i;
934
935 consdata = SCIPconsGetData(cons);
936 assert(consdata != NULL);
937 assert(consdata->rows == NULL);
938
939 nvars = consdata->nvars;
940
941 /* get memory for rows */
942 consdata->nrows = nvars + 1;
943 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->rows, consdata->nrows) );
944
945 /* creates LP rows corresponding to AND-constraint:
946 * - one additional row: resvar - v1 - ... - vn >= 1-n
947 * - for each operator variable vi: resvar - vi <= 0
948 */
949
950 /* create additional row */
951 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
952 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[0], cons, rowname, -consdata->nvars + 1.0, SCIPinfinity(scip),
954 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[0], consdata->resvar, 1.0) );
955 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[0], nvars, consdata->vars, -1.0) );
956
957 /* create operator rows */
958 for( i = 0; i < nvars; ++i )
959 {
960 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), i);
961 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[i+1], cons, rowname, -SCIPinfinity(scip), 0.0,
963 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i+1], consdata->resvar, 1.0) );
964 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[i+1], consdata->vars[i], -1.0) );
965 }
966
967 return SCIP_OKAY;
968}
969
970/** adds linear relaxation of AND-constraint to the LP */
971static
973 SCIP* scip, /**< SCIP data structure */
974 SCIP_CONS* cons, /**< constraint to check */
975 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
976 )
977{
978 SCIP_CONSDATA* consdata;
979
980 /* in the root LP we only add the weaker relaxation which consists of two rows:
981 * - one additional row: resvar - v1 - ... - vn >= 1-n
982 * - aggregated row: n*resvar - v1 - ... - vn <= 0.0
983 *
984 * during separation we separate the stronger relaxation which consists of n+1 row:
985 * - one additional row: resvar - v1 - ... - vn >= 1-n
986 * - for each operator variable vi: resvar - vi <= 0.0
987 */
988
989 consdata = SCIPconsGetData(cons);
990 assert(consdata != NULL);
991
992 /* create the aggregated row */
993 if( consdata->aggrrow == NULL )
994 {
995 char rowname[SCIP_MAXSTRLEN];
996
997 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_operators", SCIPconsGetName(cons));
998 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->aggrrow, cons, rowname, -SCIPinfinity(scip), 0.0,
1000 SCIP_CALL( SCIPaddVarToRow(scip, consdata->aggrrow, consdata->resvar, (SCIP_Real) consdata->nvars) );
1001 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->aggrrow, consdata->nvars, consdata->vars, -1.0) );
1002 }
1003
1004 /* insert aggregated LP row as cut */
1005 if( !SCIProwIsInLP(consdata->aggrrow) )
1006 {
1007 SCIP_CALL( SCIPaddRow(scip, consdata->aggrrow, FALSE, infeasible) );
1008 }
1009
1010 if( !(*infeasible) )
1011 {
1012 if( consdata->rows == NULL )
1013 {
1014 /* create the n+1 row relaxation */
1016 }
1017
1018 assert(consdata->rows != NULL);
1019
1020 /* add additional row */
1021 if( !SCIProwIsInLP(consdata->rows[0]) )
1022 {
1023 SCIP_CALL( SCIPaddRow(scip, consdata->rows[0], FALSE, infeasible) );
1024 }
1025 }
1026
1027 return SCIP_OKAY;
1028}
1029
1030/** adds constraint as row to the NLP, if not added yet */
1031static
1033 SCIP* scip, /**< SCIP data structure */
1034 SCIP_CONS* cons /**< and constraint */
1035 )
1036{
1037 SCIP_CONSDATA* consdata;
1038
1039 assert(SCIPisNLPConstructed(scip));
1040
1041 /* skip deactivated, redundant, or local constraints (the NLP does not allow for local rows at the moment) */
1042 if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsLocal(cons) )
1043 return SCIP_OKAY;
1044
1045 consdata = SCIPconsGetData(cons);
1046 assert(consdata != NULL);
1047 assert(consdata->resvar != NULL);
1048
1049 if( consdata->nlrow == NULL )
1050 {
1051 SCIP_EXPR* expr;
1052 SCIP_EXPR** varexprs;
1053 SCIP_Real minusone = -1.0;
1054 int i;
1055
1056 SCIP_CALL( SCIPallocBufferArray(scip, &varexprs, consdata->nvars) );
1057 for( i = 0; i < consdata->nvars; ++i )
1058 {
1059 SCIP_CALL( SCIPcreateExprVar(scip, &varexprs[i], consdata->vars[i], NULL, NULL) );
1060 }
1061 SCIP_CALL( SCIPcreateExprProduct(scip, &expr, consdata->nvars, varexprs, 1.0, NULL, NULL) );
1062
1063 SCIP_CALL( SCIPcreateNlRow(scip, &consdata->nlrow, SCIPconsGetName(cons),
1064 0.0, 1, &consdata->resvar, &minusone, expr, 0.0, 0.0, SCIP_EXPRCURV_UNKNOWN) );
1065 assert(consdata->nlrow != NULL);
1066
1067 SCIP_CALL( SCIPreleaseExpr(scip, &expr) );
1068 for( i = 0; i < consdata->nvars; ++i )
1069 {
1070 SCIP_CALL( SCIPreleaseExpr(scip, &varexprs[i]) );
1071 }
1072 SCIPfreeBufferArray(scip, &varexprs);
1073 }
1074
1075 if( !SCIPnlrowIsInNLP(consdata->nlrow) )
1076 {
1077 SCIP_CALL( SCIPaddNlRow(scip, consdata->nlrow) );
1078 }
1079
1080 return SCIP_OKAY;
1081}
1082
1083/** checks AND-constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
1084static
1086 SCIP* scip, /**< SCIP data structure */
1087 SCIP_CONS* cons, /**< constraint to check */
1088 SCIP_SOL* sol, /**< solution to check, NULL for current solution */
1089 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
1090 SCIP_Bool printreason, /**< Should the reason for the violation be printed? */
1091 SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
1092 )
1093{
1094 SCIP_CONSDATA* consdata;
1095 SCIP_Bool mustcheck;
1096 int r;
1097
1098 assert(violated != NULL);
1099
1100 consdata = SCIPconsGetData(cons);
1101 assert(consdata != NULL);
1102
1103 *violated = FALSE;
1104
1105 /* check whether we can skip this feasibility check, because all rows are in the LP and do not have to be checked */
1106 mustcheck = checklprows;
1107 mustcheck = mustcheck || (consdata->rows == NULL);
1108 if( !mustcheck )
1109 {
1110 assert(consdata->rows != NULL);
1111
1112 for( r = 0; r < consdata->nrows; ++r )
1113 {
1114 mustcheck = !SCIProwIsInLP(consdata->rows[r]);
1115 if( mustcheck )
1116 break;
1117 }
1118 }
1119
1120 /* check feasibility of constraint if necessary */
1121 if( mustcheck )
1122 {
1123 SCIP_Real minsolval = 1.0;
1124 SCIP_Real sumsolval = 0.0;
1125 SCIP_Real solval;
1126 SCIP_Real viol;
1127 int minsolind = 0;
1128 int i;
1129
1130 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1131 * enforcement
1132 */
1133 if( sol == NULL )
1134 {
1135 SCIP_CALL( SCIPincConsAge(scip, cons) );
1136 }
1137
1138 /* evaluate operator variables */
1139 for( i = 0; i < consdata->nvars; ++i )
1140 {
1141 solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
1142
1143 if( minsolval > solval )
1144 {
1145 minsolind = i;
1146 minsolval = solval;
1147 }
1148
1149 sumsolval += solval;
1150 }
1151
1152 /* the resultant must be at most as large as every operator
1153 * and at least as large as one minus the sum of negated operators
1154 */
1155 solval = SCIPgetSolVal(scip, sol, consdata->resvar);
1156 viol = MAX3(0.0, solval - minsolval, sumsolval - (consdata->nvars - 1.0 + solval));
1157
1158 if( SCIPisFeasPositive(scip, viol) )
1159 {
1160 *violated = TRUE;
1161
1162 /* only reset constraint age if we are in enforcement */
1163 if( sol == NULL )
1164 {
1166 }
1167
1168 if( printreason )
1169 {
1170 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
1171 SCIPinfoMessage(scip, NULL, ";\n");
1172 SCIPinfoMessage(scip, NULL, "violation:");
1173
1174 if( SCIPisFeasPositive(scip, solval - minsolval) )
1175 {
1176 SCIPinfoMessage(scip, NULL, " operand <%s> = FALSE and resultant <%s> = TRUE\n",
1177 SCIPvarGetName(consdata->vars[minsolind]), SCIPvarGetName(consdata->resvar));
1178 }
1179 else
1180 {
1181 SCIPinfoMessage(scip, NULL, " all operands are TRUE and resultant <%s> = FALSE\n",
1182 SCIPvarGetName(consdata->resvar));
1183 }
1184 }
1185 }
1186
1187 /* update constraint violation in solution */
1188 if( sol != NULL )
1189 SCIPupdateSolConsViolation(scip, sol, viol, viol);
1190 }
1191
1192 return SCIP_OKAY;
1193}
1194
1195/** separates given primal solution */
1196static
1198 SCIP* scip, /**< SCIP data structure */
1199 SCIP_CONS* cons, /**< constraint to check */
1200 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1201 SCIP_Bool* separated, /**< pointer to store whether a cut was found */
1202 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1203 )
1204{
1205 SCIP_CONSDATA* consdata;
1206 SCIP_Real feasibility;
1207 int r;
1208
1209 assert(separated != NULL);
1210 assert(cutoff != NULL);
1211
1212 *separated = FALSE;
1213 *cutoff = FALSE;
1214
1215 consdata = SCIPconsGetData(cons);
1216 assert(consdata != NULL);
1217
1218 /* create all necessary rows for the linear relaxation */
1219 if( consdata->rows == NULL )
1220 {
1222 }
1223 assert(consdata->rows != NULL);
1224
1225 /* test all rows for feasibility and add infeasible rows */
1226 for( r = 0; r < consdata->nrows; ++r )
1227 {
1228 if( !SCIProwIsInLP(consdata->rows[r]) )
1229 {
1230 feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
1231 if( SCIPisFeasNegative(scip, feasibility) )
1232 {
1233 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, cutoff) );
1234 if ( *cutoff )
1235 return SCIP_OKAY;
1236 *separated = TRUE;
1237 }
1238 }
1239 }
1240
1241 return SCIP_OKAY;
1242}
1243
1244/** analyzes conflicting TRUE assignment to resultant of given constraint, and adds conflict constraint to problem */
1245static
1247 SCIP* scip, /**< SCIP data structure */
1248 SCIP_CONS* cons, /**< AND-constraint that detected the conflict */
1249 int falsepos /**< position of operand that is fixed to FALSE */
1250 )
1251{
1252 SCIP_CONSDATA* consdata;
1253
1254 /* conflict analysis can only be applied in solving stage and if it turned on */
1256 return SCIP_OKAY;
1257
1258 consdata = SCIPconsGetData(cons);
1259 assert(consdata != NULL);
1260 assert(SCIPvarGetLbLocal(consdata->resvar) > 0.5);
1261 assert(0 <= falsepos && falsepos < consdata->nvars);
1262 assert(SCIPvarGetUbLocal(consdata->vars[falsepos]) < 0.5);
1263
1264 /* initialize conflict analysis, and add resultant and single operand variable to conflict candidate queue */
1266
1267 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1268 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[falsepos]) );
1269
1270 /* analyze the conflict */
1272
1273 return SCIP_OKAY;
1274}
1275
1276/** analyzes conflicting FALSE assignment to resultant of given constraint, and adds conflict constraint to problem */
1277static
1279 SCIP* scip, /**< SCIP data structure */
1280 SCIP_CONS* cons /**< or constraint that detected the conflict */
1281 )
1282{
1283 SCIP_CONSDATA* consdata;
1284 int v;
1285
1286 assert(!SCIPconsIsModifiable(cons));
1287
1288 /* conflict analysis can only be applied in solving stage and if it is applicable */
1290 return SCIP_OKAY;
1291
1292 consdata = SCIPconsGetData(cons);
1293 assert(consdata != NULL);
1294 assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1295
1296 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1298
1299 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1300 for( v = 0; v < consdata->nvars; ++v )
1301 {
1302 assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1303 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
1304 }
1305
1306 /* analyze the conflict */
1308
1309 return SCIP_OKAY;
1310}
1311
1312/** tries to fix the given resultant to zero */
1313static
1315 SCIP* scip, /**< SCIP data structure */
1316 SCIP_CONS* cons, /**< AND-constraint to be processed */
1317 SCIP_VAR* resvar, /**< resultant variable to fix to zero */
1318 int pos, /**< position of operand that is fixed to FALSE */
1319 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1320 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1321 )
1322{
1323 SCIP_Bool infeasible;
1324 SCIP_Bool tightened;
1325
1326 SCIPdebugMsg(scip, "constraint <%s>: operator %d fixed to 0.0 -> fix resultant <%s> to 0.0\n",
1327 SCIPconsGetName(cons), pos, SCIPvarGetName(resvar));
1328
1329 SCIP_CALL( SCIPinferBinvarCons(scip, resvar, FALSE, cons, (int)PROPRULE_1, &infeasible, &tightened) );
1330
1331 if( infeasible )
1332 {
1333 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1334 SCIP_CALL( analyzeConflictOne(scip, cons, pos) );
1336 (*cutoff) = TRUE;
1337 }
1338 else
1339 {
1341 if( tightened )
1342 {
1344 (*nfixedvars)++;
1345 }
1346 }
1347
1348 return SCIP_OKAY;
1349}
1350
1351/** fix all operands to one */
1352static
1354 SCIP* scip, /**< SCIP data structure */
1355 SCIP_CONS* cons, /**< AND-constraint to be processed */
1356 SCIP_VAR** vars, /**< array of operands */
1357 int nvars, /**< number of operands */
1358 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1359 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1360 )
1361{
1362 SCIP_Bool infeasible;
1363 SCIP_Bool tightened;
1364 int v;
1365
1366 for( v = 0; v < nvars && !(*cutoff); ++v )
1367 {
1368 SCIPdebugMsg(scip, "constraint <%s>: resultant fixed to 1.0 -> fix operator var <%s> to 1.0\n",
1369 SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
1370
1371 SCIP_CALL( SCIPinferBinvarCons(scip, vars[v], TRUE, cons, (int)PROPRULE_2, &infeasible, &tightened) );
1372
1373 if( infeasible )
1374 {
1375 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1376 SCIP_CALL( analyzeConflictOne(scip, cons, v) );
1378 (*cutoff) = TRUE;
1379 }
1380 else if( tightened )
1381 {
1383 (*nfixedvars)++;
1384 }
1385 }
1386
1387 if( !(*cutoff) )
1388 {
1390 }
1391
1392 return SCIP_OKAY;
1393}
1394
1395/** linearize AND-constraint due to a globally to zero fixed resultant; that is, creates, adds, and releases a logicor
1396 * constraint and remove the AND-constraint globally.
1397 *
1398 * Since the resultant is fixed to zero the AND-constraint collapses to linear constraint of the form:
1399 *
1400 * - \f$\sum_{i=0}^{n-1} v_i \leq n-1\f$
1401 *
1402 * This can be transformed into a logicor constraint of the form
1403 *
1404 * - \f$\sum_{i=0}^{n-1} ~v_i \geq 1\f$
1405 */
1406static
1408 SCIP* scip, /**< SCIP data structure */
1409 SCIP_CONS* cons, /**< AND-constraint to linearize */
1410 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1411 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1412 int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1413 )
1414{
1415 SCIP_CONSDATA* consdata;
1416 SCIP_VAR** vars;
1417 SCIP_CONS* lincons;
1418 SCIP_Bool conscreated;
1419 int nvars;
1420
1421 consdata = SCIPconsGetData(cons);
1422 assert(consdata != NULL);
1423
1424 assert(!(*cutoff));
1425 assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
1426
1427 nvars = consdata->nvars;
1428 conscreated = FALSE;
1429
1430 /* allocate memory for variables for updated constraint */
1431 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
1432
1433 /* if we only have two variables, we prefer a set packing constraint instead of a logicor constraint */
1434 if( nvars == 2 && !SCIPconsIsModifiable(cons) )
1435 {
1436 SCIP_Bool* negated;
1437 SCIP_Bool infeasible;
1438 SCIP_Bool tightened;
1439
1440 /* get active representation */
1441 SCIP_CALL( SCIPallocBufferArray(scip, &negated, nvars) );
1442 SCIP_CALL( SCIPgetBinvarRepresentatives(scip, nvars, consdata->vars, vars, negated) );
1443 SCIPfreeBufferArray(scip, &negated);
1444
1445 /* if one of the two operators is globally fixed to one it follows that the other has to be zero */
1446 if( SCIPvarGetLbGlobal(vars[0]) > 0.5 )
1447 {
1448 SCIP_CALL( SCIPfixVar(scip, vars[1], 0.0, &infeasible, &tightened) );
1449
1450 if( infeasible )
1451 *cutoff = TRUE;
1452 else if( tightened )
1453 ++(*nfixedvars);
1454 }
1455 else if( SCIPvarGetLbGlobal(vars[1]) > 0.5 )
1456 {
1457 SCIP_CALL( SCIPfixVar(scip, vars[0], 0.0, &infeasible, &tightened) );
1458
1459 if( infeasible )
1460 *cutoff = TRUE;
1461 else if( tightened )
1462 ++(*nfixedvars);
1463 }
1464 else if( SCIPvarGetUbGlobal(vars[0]) > 0.5 && SCIPvarGetUbGlobal(vars[1]) > 0.5 )
1465 {
1466 /* create, add, and release the setppc constraint */
1467 SCIP_CALL( SCIPcreateConsSetpack(scip, &lincons, SCIPconsGetName(cons), nvars, vars,
1469 consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1471 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1472
1473 conscreated = TRUE;
1474 }
1475 }
1476 else
1477 {
1478 int v;
1479
1480 /* collect negated variables */
1481 for( v = 0; v < nvars; ++v )
1482 {
1483 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &vars[v]) );
1484 }
1485
1486 /* create, add, and release the logicor constraint */
1487 SCIP_CALL( SCIPcreateConsLogicor(scip, &lincons, SCIPconsGetName(cons), nvars, vars,
1489 consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1491 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1492
1493 conscreated = TRUE;
1494 }
1495
1496 if( conscreated )
1497 {
1498 /* add and release new constraint */
1499 SCIPdebugPrintCons(scip, lincons, NULL); /*lint !e644*/
1500 SCIP_CALL( SCIPaddCons(scip, lincons) ); /*lint !e644*/
1501 SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); /*lint !e644*/
1502
1503 ++(*nupgdconss);
1504 }
1505
1506 /* remove the AND-constraint globally */
1507 SCIP_CALL( SCIPdelCons(scip, cons) );
1508
1509 /* delete temporary memory */
1510 SCIPfreeBufferArray(scip, &vars);
1511
1512 return SCIP_OKAY;
1513}
1514
1515/** the resultant is fixed to zero; in case all except one operator are fixed to TRUE the last operator has to fixed to FALSE */
1516/** @note consdata->watchedvars might not be the same to the watchedvar parameters, because the update was not yet done */
1517static
1519 SCIP* scip, /**< SCIP data structure */
1520 SCIP_CONS* cons, /**< AND-constraint to be processed */
1521 int watchedvar1, /**< maybe last unfixed variable position */
1522 int watchedvar2, /**< second watched position */
1523 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1524 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1525 )
1526{
1527 SCIP_CONSDATA* consdata;
1528
1529 consdata = SCIPconsGetData(cons);
1530 assert(consdata != NULL);
1531 assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1532
1533 if( watchedvar2 == -1 )
1534 {
1535 SCIP_Bool infeasible;
1536 SCIP_Bool tightened;
1537
1538 assert(watchedvar1 != -1);
1539
1540#ifndef NDEBUG
1541 /* check that all variables regardless of wathcedvar1 are fixed to 1 */
1542 {
1543 int v;
1544
1545 for( v = consdata->nvars - 1; v >= 0; --v )
1546 if( v != watchedvar1 )
1547 assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1548 }
1549#endif
1550
1551 SCIPdebugMsg(scip, "constraint <%s>: resultant <%s> fixed to 0.0, only one unfixed operand -> fix operand <%s> to 0.0\n",
1552 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar), SCIPvarGetName(consdata->vars[watchedvar1]));
1553
1554 SCIP_CALL( SCIPinferBinvarCons(scip, consdata->vars[watchedvar1], FALSE, cons, (int)PROPRULE_4, &infeasible, &tightened) );
1555
1556 if( infeasible )
1557 {
1558 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1561 *cutoff = TRUE;
1562 }
1563 else
1564 {
1566 if( tightened )
1567 {
1569 (*nfixedvars)++;
1570 }
1571 }
1572 }
1573
1574 return SCIP_OKAY;
1575}
1576
1577/** replaces multiple occurrences of variables */
1578static
1580 SCIP* scip, /**< SCIP data structure */
1581 SCIP_CONS* cons, /**< AND-constraint */
1582 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1583 unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
1584 int* nentries, /**< pointer for array size, if array will be to small it's corrected */
1585 int* nfixedvars, /**< pointer to store number of fixed variables */
1586 int* nchgcoefs, /**< pointer to store number of changed coefficients */
1587 int* ndelconss /**< pointer to store number of deleted constraints */
1588 )
1589{
1590 SCIP_CONSDATA* consdata;
1591 SCIP_VAR** vars;
1592 SCIP_VAR* var;
1593 SCIP_VAR* probvar;
1594 int probidx;
1595 int nvars;
1596 int v;
1597#ifndef NDEBUG
1598 int nbinvars;
1599 int nintvars;
1600 int nimplvars;
1601#endif
1602
1603 assert(scip != NULL);
1604 assert(cons != NULL);
1605 assert(eventhdlr != NULL);
1606 assert(*entries != NULL);
1607 assert(nentries != NULL);
1608 assert(nfixedvars != NULL);
1609 assert(nchgcoefs != NULL);
1610 assert(ndelconss != NULL);
1611
1612 consdata = SCIPconsGetData(cons);
1613 assert(consdata != NULL);
1614
1615 if( consdata->merged )
1616 return SCIP_OKAY;
1617
1618 /* nothing to merge */
1619 if( consdata->nvars <= 1 )
1620 {
1621 consdata->merged = TRUE;
1622 return SCIP_OKAY;
1623 }
1624
1625 vars = consdata->vars;
1626 nvars = consdata->nvars;
1627
1628 assert(vars != NULL);
1629 assert(nvars >= 2);
1630
1631#ifndef NDEBUG
1632 nbinvars = SCIPgetNBinVars(scip);
1633 nintvars = SCIPgetNIntVars(scip);
1634 nimplvars = SCIPgetNImplVars(scip);
1635 assert(*nentries >= nbinvars + nintvars + nimplvars);
1636#endif
1637
1638 /* initialize entries array */
1639 for( v = nvars - 1; v >= 0; --v )
1640 {
1641 var = vars[v];
1642 assert(var != NULL);
1644
1645 probvar = (SCIPvarIsActive(var) ? var : SCIPvarGetNegatedVar(var));
1646 assert(probvar != NULL);
1647
1648 probidx = SCIPvarGetProbindex(probvar);
1649 assert(0 <= probidx);
1650
1651 /* check variable type, either pure binary or an integer/implicit integer variable with 0/1 bounds */
1652 assert((probidx < nbinvars && SCIPvarGetType(probvar) == SCIP_VARTYPE_BINARY)
1653 || (SCIPvarIsBinary(probvar) &&
1654 ((probidx >= nbinvars && probidx < nbinvars + nintvars && SCIPvarGetType(probvar) == SCIP_VARTYPE_INTEGER) ||
1655 (probidx >= nbinvars + nintvars && probidx < nbinvars + nintvars + nimplvars &&
1656 SCIPvarGetType(probvar) == SCIP_VARTYPE_IMPLINT))));
1657
1658 /* var is not active yet */
1659 (*entries)[probidx] = 0;
1660 }
1661
1662 /* search for multiple variables; scan from back to front because deletion doesn't affect the order of the front
1663 * variables
1664 * @note don't reorder variables because we would loose the watched variables and filter position inforamtion
1665 */
1666 for( v = nvars - 1; v >= 0; --v )
1667 {
1668 var = vars[v];
1669 assert(var != NULL);
1671
1672 probvar = (SCIPvarIsActive(var) ? var : SCIPvarGetNegatedVar(var));
1673 assert(probvar != NULL);
1674
1675 probidx = SCIPvarGetProbindex(probvar);
1676 assert(0 <= probidx && probidx < *nentries);
1677
1678 /* if var occurs first time in constraint init entries array */
1679 if( (*entries)[probidx] == 0 )
1680 {
1681 (*entries)[probidx] = (SCIPvarIsActive(var) ? 1 : 2);
1682 }
1683 /* if var occurs second time in constraint, first time it was not negated */
1684 else if( ((*entries)[probidx] == 1 && SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && !SCIPvarIsActive(var)) )
1685 {
1686 /* delete the multiple variable */
1687 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1688 ++(*nchgcoefs);
1689 }
1690 else
1691 {
1692 SCIP_Bool infeasible;
1693 SCIP_Bool fixed;
1694
1695 assert(((*entries)[probidx] == 1 && !SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && SCIPvarIsActive(var)));
1696
1697 SCIPdebugMsg(scip, "AND-constraint <%s> is redundant: variable <%s> and its negation are present -> fix resultant <%s> = 0\n",
1698 SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetName(consdata->resvar));
1699
1700 /* negation of the variable is already present in the constraint: fix resultant to zero */
1701#ifndef NDEBUG
1702 {
1703 int i;
1704 for( i = consdata->nvars - 1; i > v && var != SCIPvarGetNegatedVar(vars[i]); --i )
1705 {}
1706 assert(i > v);
1707 }
1708#endif
1709
1710 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
1711 assert(!infeasible);
1712 if( fixed )
1713 ++(*nfixedvars);
1714
1715 SCIP_CALL( SCIPdelCons(scip, cons) );
1716 break;
1717 }
1718 }
1719
1720 consdata->merged = TRUE;
1721
1722 return SCIP_OKAY;
1723}
1724
1725/** propagates constraint with the following rules:
1726 * (1) v_i = FALSE => r = FALSE
1727 * (2) r = TRUE => v_i = TRUE for all i
1728 * (3) v_i = TRUE for all i => r = TRUE
1729 * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1730 *
1731 * additional if the resultant is fixed to zero during presolving or in the root node (globally), then the
1732 * AND-constraint is collapsed to a linear (logicor) constraint of the form
1733 * -> sum_{i=0}^{n-1} ~v_i >= 1
1734 */
1735static
1737 SCIP* scip, /**< SCIP data structure */
1738 SCIP_CONS* cons, /**< AND-constraint to be processed */
1739 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1740 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1741 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1742 int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1743 )
1744{
1745 SCIP_CONSDATA* consdata;
1746 SCIP_VAR* resvar;
1747 SCIP_VAR** vars;
1748 int nvars;
1749 int watchedvar1;
1750 int watchedvar2;
1751 int i;
1752 SCIP_Bool infeasible;
1753 SCIP_Bool tightened;
1754
1755 assert(cutoff != NULL);
1756 assert(nfixedvars != NULL);
1757
1758 consdata = SCIPconsGetData(cons);
1759 assert(consdata != NULL);
1760
1761 resvar = consdata->resvar;
1762 vars = consdata->vars;
1763 nvars = consdata->nvars;
1764
1765 /* don't process the constraint, if none of the operator variables was fixed to FALSE, and if the watched variables
1766 * and the resultant weren't fixed to any value since last propagation call
1767 */
1768 if( consdata->propagated )
1769 {
1770 assert(consdata->nofixedzero);
1771 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(resvar), 0.0));
1772 return SCIP_OKAY;
1773 }
1774
1775 /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
1777 {
1778 SCIP_CALL( SCIPincConsAge(scip, cons) );
1779 }
1780
1781 /* if one of the operator variables was fixed to FALSE, the resultant can be fixed to FALSE (rule (1)) */
1782 if( !consdata->nofixedzero )
1783 {
1784 for( i = 0; i < nvars && SCIPvarGetUbLocal(vars[i]) > 0.5; ++i ) /* search for operator fixed to zero */
1785 {}
1786 if( i < nvars )
1787 {
1788 /* fix resultant to zero */
1789 SCIP_CALL( consdataFixResultantZero(scip, cons, resvar, i, cutoff, nfixedvars) );
1790 }
1791 else
1792 consdata->nofixedzero = TRUE;
1793 }
1794
1795 /* check if resultant variables is globally fixed to zero */
1796 if( !SCIPinProbing(scip) && SCIPvarGetUbGlobal(resvar) < 0.5 )
1797 {
1798 SCIP_CALL( consdataLinearize(scip, cons, cutoff, nfixedvars, nupgdconss) );
1799
1800 if( *cutoff && SCIPgetDepth(scip) > 0 )
1801 {
1802 /* we are done with solving since a global bound change was infeasible */
1804 }
1805
1806 return SCIP_OKAY;
1807 }
1808
1809 /* if the resultant and at least one operand are locally fixed to zero, the constraint is locally redundant */
1810 if( SCIPvarGetUbLocal(resvar) < 0.5 && !consdata->nofixedzero )
1811 {
1813 return SCIP_OKAY;
1814 }
1815
1816 /* if resultant is fixed to TRUE, all operator variables can be fixed to TRUE (rule (2)) */
1817 if( SCIPvarGetLbLocal(resvar) > 0.5 )
1818 {
1819 /* fix operands to one */
1820 SCIP_CALL( consdataFixOperandsOne(scip, cons, vars, nvars, cutoff, nfixedvars) );
1821
1822 return SCIP_OKAY;
1823 }
1824
1825 /* rules (3) and (4) can only be applied, if we know all operator variables */
1826 if( SCIPconsIsModifiable(cons) )
1827 return SCIP_OKAY;
1828
1829 /* rules (3) and (4) cannot be applied, if we have at least two unfixed variables left;
1830 * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
1831 * if these ones get fixed
1832 */
1833 watchedvar1 = consdata->watchedvar1;
1834 watchedvar2 = consdata->watchedvar2;
1835
1836 /* check, if watched variables are still unfixed */
1837 if( watchedvar1 != -1 )
1838 {
1839 assert(SCIPvarGetUbLocal(vars[watchedvar1]) > 0.5); /* otherwise, rule (1) could be applied */
1840 if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 )
1841 watchedvar1 = -1;
1842 }
1843 if( watchedvar2 != -1 )
1844 {
1845 assert(SCIPvarGetUbLocal(vars[watchedvar2]) > 0.5); /* otherwise, rule (1) could be applied */
1846 if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 )
1847 watchedvar2 = -1;
1848 }
1849
1850 /* if only one watched variable is still unfixed, make it the first one */
1851 if( watchedvar1 == -1 )
1852 {
1853 watchedvar1 = watchedvar2;
1854 watchedvar2 = -1;
1855 }
1856 assert(watchedvar1 != -1 || watchedvar2 == -1);
1857
1858 /* if the watched variables are invalid (fixed), find new ones if existing */
1859 if( watchedvar2 == -1 )
1860 {
1861 for( i = 0; i < nvars; ++i )
1862 {
1863 assert(SCIPvarGetUbLocal(vars[i]) > 0.5); /* otherwise, rule (1) could be applied */
1864 if( SCIPvarGetLbLocal(vars[i]) < 0.5 )
1865 {
1866 if( watchedvar1 == -1 )
1867 {
1868 assert(watchedvar2 == -1);
1869 watchedvar1 = i;
1870 }
1871 else if( watchedvar1 != i )
1872 {
1873 watchedvar2 = i;
1874 break;
1875 }
1876 }
1877 }
1878 }
1879 assert(watchedvar1 != -1 || watchedvar2 == -1);
1880
1881 /* if all variables are fixed to TRUE, the resultant can also be fixed to TRUE (rule (3)) */
1882 if( watchedvar1 == -1 )
1883 {
1884 assert(watchedvar2 == -1);
1885
1886 SCIPdebugMsg(scip, "constraint <%s>: all operator vars fixed to 1.0 -> fix resultant <%s> to 1.0\n",
1887 SCIPconsGetName(cons), SCIPvarGetName(resvar));
1888 SCIP_CALL( SCIPinferBinvarCons(scip, resvar, TRUE, cons, (int)PROPRULE_3, &infeasible, &tightened) );
1889
1890 if( infeasible )
1891 {
1892 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1895 *cutoff = TRUE;
1896 }
1897 else
1898 {
1900 if( tightened )
1901 {
1903 (*nfixedvars)++;
1904 }
1905 }
1906
1907 return SCIP_OKAY;
1908 }
1909
1910 /* if resultant is fixed to FALSE, and only one operator variable is not fixed to TRUE, this operator variable
1911 * can be fixed to FALSE (rule (4))
1912 */
1913 if( watchedvar2 == -1 && SCIPvarGetUbLocal(resvar) < 0.5 )
1914 {
1915 assert(watchedvar1 != -1);
1916
1917 SCIP_CALL( analyzeZeroResultant(scip, cons, watchedvar1, watchedvar2, cutoff, nfixedvars) );
1918
1919 return SCIP_OKAY;
1920 }
1921
1922 /* switch to the new watched variables */
1923 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
1924
1925 /* mark the constraint propagated if we have an unfixed resultant or are not in probing, it is necessary that a fixed
1926 * resulting in probing mode does not lead to a propagated constraint, because the constraint upgrade needs to be performed
1927 */
1928 consdata->propagated = (!SCIPinProbing(scip) || (SCIPvarGetLbLocal(consdata->resvar) < 0.5 && SCIPvarGetUbLocal(consdata->resvar) > 0.5));
1929
1930 return SCIP_OKAY;
1931}
1932
1933/** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
1934 * propagation rule (see propagateCons()):
1935 * (1) v_i = FALSE => r = FALSE
1936 * (2) r = TRUE => v_i = TRUE for all i
1937 * (3) v_i = TRUE for all i => r = TRUE
1938 * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1939 */
1940static
1942 SCIP* scip, /**< SCIP data structure */
1943 SCIP_CONS* cons, /**< constraint that inferred the bound change */
1944 SCIP_VAR* infervar, /**< variable that was deduced */
1945 PROPRULE proprule, /**< propagation rule that deduced the value */
1946 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1947 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1948 )
1949{
1950 SCIP_CONSDATA* consdata;
1951 SCIP_VAR** vars;
1952 int nvars;
1953 int i;
1954
1955 assert(result != NULL);
1956
1957 consdata = SCIPconsGetData(cons);
1958 assert(consdata != NULL);
1959 vars = consdata->vars;
1960 nvars = consdata->nvars;
1961
1962 switch( proprule )
1963 {
1964 case PROPRULE_1:
1965 /* the resultant was inferred to FALSE, because one operand variable was FALSE */
1966 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
1967 assert(infervar == consdata->resvar);
1968 for( i = 0; i < nvars; ++i )
1969 {
1970 if( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
1971 {
1973 break;
1974 }
1975 }
1976 assert(i < nvars);
1977 *result = SCIP_SUCCESS;
1978 break;
1979
1980 case PROPRULE_2:
1981 /* the operand variable was inferred to TRUE, because the resultant was TRUE */
1982 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1983 assert(SCIPgetVarLbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) > 0.5);
1984 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1985 *result = SCIP_SUCCESS;
1986 break;
1987
1988 case PROPRULE_3:
1989 /* the resultant was inferred to TRUE, because all operand variables were TRUE */
1990 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1991 assert(infervar == consdata->resvar);
1992 for( i = 0; i < nvars; ++i )
1993 {
1994 assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
1996 }
1997 *result = SCIP_SUCCESS;
1998 break;
1999
2000 case PROPRULE_4:
2001 /* the operand variable was inferred to FALSE, because the resultant was FALSE and all other operands were TRUE */
2002 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2003 assert(SCIPgetVarUbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) < 0.5);
2004 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
2005 for( i = 0; i < nvars; ++i )
2006 {
2007 if( vars[i] != infervar )
2008 {
2009 assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
2011 }
2012 }
2013 *result = SCIP_SUCCESS;
2014 break;
2015
2016 case PROPRULE_INVALID:
2017 default:
2018 SCIPerrorMessage("invalid inference information %d in AND-constraint <%s>\n", proprule, SCIPconsGetName(cons));
2019 return SCIP_INVALIDDATA;
2020 }
2021
2022 return SCIP_OKAY;
2023}
2024
2025/** perform dual presolving on AND-constraints */
2026static
2028 SCIP* scip, /**< SCIP data structure */
2029 SCIP_CONS** conss, /**< AND-constraints to perform dual presolving on */
2030 int nconss, /**< number of AND-constraints */
2031 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2032 unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
2033 int* nentries, /**< pointer for array size, if array will be to small it's corrected */
2034 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2035 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
2036 int* naggrvars, /**< pointer to add up the number of aggregated variables */
2037 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
2038 int* ndelconss, /**< pointer to add up the number of deleted constraints */
2039 int* nupgdconss, /**< pointer to add up the number of upgraded constraints */
2040 int* naddconss /**< pointer to add up the number of added constraints */
2041 )
2042{
2043 SCIP_CONS* cons;
2044 SCIP_CONSDATA* consdata;
2045 SCIP_VAR** impoperands;
2046 SCIP_VAR** vars;
2047 SCIP_VAR* resvar;
2048 SCIP_VAR* var;
2049 int nimpoperands;
2050 int nvars;
2051 int size;
2052 int v;
2053 int c;
2054 SCIP_Bool infeasible;
2055 SCIP_Bool fixed;
2056
2057 assert(scip != NULL);
2058 assert(conss != NULL || nconss == 0);
2059 assert(eventhdlr != NULL);
2060 assert(*entries != NULL);
2061 assert(nentries != NULL);
2062 assert(cutoff != NULL);
2063 assert(nfixedvars != NULL);
2064 assert(naggrvars != NULL);
2065 assert(nchgcoefs != NULL);
2066 assert(ndelconss != NULL);
2067 assert(nupgdconss != NULL);
2068 assert(naddconss != NULL);
2069
2070 if( nconss == 0 )
2071 return SCIP_OKAY;
2072
2073 assert(conss != NULL);
2074
2075 size = 2 * (SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip));
2076
2077 SCIP_CALL( SCIPallocBufferArray(scip, &impoperands, size) );
2078
2079 for( c = nconss - 1; c >= 0 && !(*cutoff); --c )
2080 {
2081 cons = conss[c];
2082 assert(cons != NULL);
2083
2084 if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsModifiable(cons) )
2085 continue;
2086
2087 /* propagate constraint */
2088 SCIP_CALL( propagateCons(scip, cons, eventhdlr, cutoff, nfixedvars, nupgdconss) );
2089
2090 if( !SCIPconsIsActive(cons) )
2091 continue;
2092
2093 if( *cutoff )
2094 break;
2095
2096 SCIP_CALL( applyFixings(scip, cons, eventhdlr, nchgcoefs) );
2097
2098 /* merge multiple occurances of variables or variables with their negated variables */
2099 SCIP_CALL( mergeMultiples(scip, cons, eventhdlr, entries, nentries, nfixedvars, nchgcoefs, ndelconss) );
2100
2101 if( !SCIPconsIsActive(cons) )
2102 continue;
2103
2104 consdata = SCIPconsGetData(cons);
2105 assert(consdata != NULL);
2106
2107 vars = consdata->vars;
2108 nvars = consdata->nvars;
2109 assert(vars != NULL || nvars == 0);
2110
2111 if( nvars == 0 )
2112 continue;
2113
2114 assert(vars != NULL);
2115
2116 resvar = consdata->resvar;
2117 assert(resvar != NULL);
2118 /* a fixed resultant needs to be removed, otherwise we might fix operands to a wrong value later on */
2119 assert(SCIPvarGetLbGlobal(resvar) < 0.5 && SCIPvarGetUbGlobal(resvar) > 0.5);
2120 assert(SCIPvarGetNLocksUpType(resvar, SCIP_LOCKTYPE_MODEL) >= 1
2122
2125 {
2126 SCIP_Real resobj;
2127 SCIP_Real obj;
2128 SCIP_Real posobjsum = 0;
2129 SCIP_Real maxobj = -SCIPinfinity(scip);
2130 int maxpos = -1;
2131 int oldnfixedvars = *nfixedvars;
2132 int oldnaggrvars = *naggrvars;
2133
2134 nimpoperands = 0;
2135
2136 /* collect important operands */
2137 for( v = nvars - 1; v >= 0; --v )
2138 {
2139 var = vars[v];
2140 assert(var != NULL);
2143
2146 {
2147 impoperands[nimpoperands] = var;
2148 ++nimpoperands;
2149
2150 /* get aggregated objective value of active variable */
2151 SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2152
2153 /* add up all positive objective values of operands which have exactly one lock in both directions */
2154 if( obj > 0 )
2155 posobjsum += obj;
2156
2157 /* memorize maximal objective value of operands and its position */
2158 if( obj > maxobj )
2159 {
2160 maxpos = nimpoperands - 1;
2161 maxobj = obj;
2162 }
2163 }
2164 }
2165 assert(nimpoperands >= 0 && nimpoperands <= nvars);
2166
2167 /* no dual fixable variables found */
2168 if( nimpoperands == 0 )
2169 continue;
2170
2171 /* get aggregated objective value of active variable */
2172 SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &resobj) );
2173
2174 /* resultant contributes to the objective with a negative value */
2175 if( SCIPisLE(scip, resobj, 0.0) )
2176 {
2177 SCIP_Bool poscontissmall = SCIPisLE(scip, posobjsum, REALABS(resobj));
2178
2179 /* if all variables are only locked by this constraint and the resultants contribution more then compensates
2180 * the positive contribution, we can fix all variables to 1
2181 */
2182 if( nimpoperands == nvars && poscontissmall )
2183 {
2184 SCIPdebugMsg(scip, "dual-fixing all variables in constraint <%s> to 1\n", SCIPconsGetName(cons));
2185
2186 SCIP_CALL( SCIPfixVar(scip, resvar, 1.0, &infeasible, &fixed) );
2187
2188 *cutoff = *cutoff || infeasible;
2189 if( fixed )
2190 ++(*nfixedvars);
2191
2192 for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2193 {
2194 SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2195
2196 *cutoff = *cutoff || infeasible;
2197 if( fixed )
2198 ++(*nfixedvars);
2199 }
2200
2201 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed to one\n", SCIPconsGetName(cons));
2202
2203 SCIP_CALL( SCIPdelCons(scip, cons) );
2204 ++(*ndelconss);
2205 }
2206 else
2207 {
2208 SCIP_Bool aggregationperformed = FALSE;
2209 SCIP_Bool zerofix = FALSE;
2210
2211 assert(nimpoperands > 0);
2212
2213 SCIPdebugMsg(scip, "dual-fixing all variables in constraint <%s> with positive contribution (when together exceeding the negative contribution of the resultant) to 0 and with negative contribution to 1\n", SCIPconsGetName(cons));
2214
2215 for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2216 {
2217 /* get aggregated objective value of active variable */
2218 SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[v], &obj) );
2219
2220 if( SCIPisLE(scip, obj, 0.0) )
2221 {
2222 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2223
2224 *cutoff = *cutoff || infeasible;
2225 if( fixed )
2226 ++(*nfixedvars);
2227 }
2228 else if( !poscontissmall )
2229 {
2230 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2231 assert(!infeasible);
2232 assert(fixed);
2233
2234 ++(*nfixedvars);
2235 zerofix = TRUE;
2236 }
2237 else
2238 {
2239 SCIP_Bool redundant;
2240 SCIP_Bool aggregated;
2241
2242 /* aggregate resultant to operand */
2243 SCIP_CALL( SCIPaggregateVars(scip, resvar, impoperands[v], 1.0, -1.0, 0.0,
2244 &infeasible, &redundant, &aggregated) );
2245 assert(!infeasible);
2246
2247 if( aggregated )
2248 {
2249 /* note that we cannot remove the aggregated operand because we do not know the position */
2250 ++(*naggrvars);
2251
2252 aggregationperformed = TRUE;
2253
2254 SCIPdebugMsg(scip, "dual aggregating operand <%s> with 1 up- and downlock to the resultant <%s> in constraint <%s>\n", SCIPvarGetName(impoperands[v]), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2255 }
2256 }
2257 }
2258 assert(*nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars <= nimpoperands);
2259
2260 /* did we aggregate the resultant, then we can decide the value to fix it on the (aggregated) objective
2261 * value since it was a independant variable
2262 */
2263 if( aggregationperformed || zerofix )
2264 {
2265 SCIP_Real fixval;
2266
2267 if( zerofix )
2268 fixval = 0.0;
2269 else
2270 {
2271 /* get aggregated objective value of active variable, that might be changed */
2272 SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &obj) );
2273 assert(!SCIPisPositive(scip, obj));
2274
2275 fixval = (SCIPisNegative(scip, obj) ? 1.0 : 0.0);
2276 }
2277
2278 if( fixval < 0.5 || *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars == nvars )
2279 {
2280 SCIPdebugMsg(scip, "constraint <%s> we can fix the resultant <%s> to %g, because the AND-constraint will alwys be fulfilled\n", SCIPconsGetName(cons), SCIPvarGetName(resvar), fixval);
2281
2282 SCIP_CALL( SCIPfixVar(scip, resvar, fixval, &infeasible, &fixed) );
2283 assert(!infeasible);
2284 assert(fixed);
2285
2286 ++(*nfixedvars);
2287
2288 SCIPdebugMsg(scip, "deleting constraint <%s> because \n", SCIPconsGetName(cons));
2289
2290 SCIP_CALL( SCIPdelCons(scip, cons) );
2291 ++(*ndelconss);
2292 }
2293 }
2294 }
2295 }
2296 /* resultant contributes to the objective with a positive value */
2297 else
2298 {
2299 SCIP_Bool zerofix = FALSE;
2300#ifndef NDEBUG
2301 SCIP_Real tmpobj;
2302
2303 assert(nimpoperands > 0);
2304 assert(maxpos >= 0 && maxpos <= consdata->nvars);
2305 assert(!SCIPisInfinity(scip, -maxobj));
2306 SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[maxpos], &tmpobj) );
2307 assert(SCIPisEQ(scip, tmpobj, maxobj));
2308#endif
2309
2310 /* if the smallest possible contribution is negative, but does not compensate the positive contribution of
2311 * the resultant we need to fix this variable to 0
2312 */
2313 if( nimpoperands == nvars && SCIPisLE(scip, maxobj, 0.0) )
2314 {
2315 SCIP_Real fixval = (SCIPisLE(scip, REALABS(maxobj), resobj) ? 0.0 : 1.0);
2316
2317 SCIPdebugMsg(scip, "dual-fixing variable <%s> in constraint <%s> to %g, because the contribution is%s " \
2318 "enough to nullify/exceed the contribution of the resultant \n",
2319 SCIPvarGetName(impoperands[maxpos]), SCIPconsGetName(cons), fixval, (fixval < 0.5) ? " not" : "");
2320
2321 SCIP_CALL( SCIPfixVar(scip, impoperands[maxpos], fixval, &infeasible, &fixed) );
2322 zerofix = (fixval < 0.5);
2323
2324 *cutoff = *cutoff || infeasible;
2325 if( fixed )
2326 ++(*nfixedvars);
2327 }
2328
2329 SCIPdebugMsg(scip, "dual-fixing all variables, except the variable with the highest contribution to " \
2330 "the objective, in constraint <%s> with positive contribution to 0 and with negative contribution to 1\n",
2331 SCIPconsGetName(cons));
2332
2333 for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2334 {
2335 /* get aggregated objective value of active variable */
2336 SCIP_CALL( SCIPvarGetAggregatedObj(impoperands[v], &obj) );
2337
2338 if( SCIPisLE(scip, obj, 0.0) )
2339 {
2340 if( v == maxpos )
2341 continue;
2342
2343 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2344 }
2345 else
2346 {
2347 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2348 zerofix = TRUE;
2349 }
2350
2351 *cutoff = *cutoff || infeasible;
2352 if( fixed )
2353 ++(*nfixedvars);
2354 }
2355 assert(*nfixedvars - oldnfixedvars <= nimpoperands);
2356 /* iff we have fixed all variables, all variables needed to be stored in the impoperands array */
2357 assert((*nfixedvars - oldnfixedvars == nvars) == (nimpoperands == nvars));
2358
2359 if( *nfixedvars - oldnfixedvars == nvars )
2360 {
2361 SCIPdebugMsg(scip, "all operands are fixed in constraint <%s> => fix resultant <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(resvar), (zerofix ? 0.0 : 1.0));
2362
2363 SCIP_CALL( SCIPfixVar(scip, resvar, zerofix ? 0.0 : 1.0, &infeasible, &fixed) );
2364
2365 *cutoff = *cutoff || infeasible;
2366 if( fixed )
2367 ++(*nfixedvars);
2368
2369 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed\n", SCIPconsGetName(cons));
2370
2371 SCIP_CALL( SCIPdelCons(scip, cons) );
2372 ++(*ndelconss);
2373 }
2374 }
2375 }
2376 /* resultant is lock by another constraint (handler), check for operands with only one down- and uplock */
2377 else
2378 {
2379 SCIP_Real maxobj = -SCIPinfinity(scip);
2380 SCIP_Real resobj;
2381 SCIP_Real obj;
2382 SCIP_Bool redundant;
2383 SCIP_Bool aggregated;
2384 SCIP_Bool resobjispos;
2385 SCIP_Bool linearize = FALSE;
2386 SCIP_Bool zerofix = FALSE;
2387#ifndef NDEBUG
2388 int oldnchgcoefs = *nchgcoefs;
2389 int oldnfixedvars = *nfixedvars;
2390#endif
2391
2392 /* get aggregated objective value of active variable */
2393 SCIP_CALL( SCIPvarGetAggregatedObj(resvar, &resobj) );
2394
2395 resobjispos = SCIPisGT(scip, resobj, 0.0);
2396
2397 /* we can only aggregate when the objective contribution of the resultant is less or equal to 0 */
2398 if( !resobjispos )
2399 {
2400 SCIP_Bool goodvarsfound = FALSE;
2401
2402 for( v = nvars - 1; v >= 0; --v )
2403 {
2404 var = vars[v];
2405 assert(var != NULL);
2408
2409 /* get aggregated objective value of active variable */
2410 SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2411
2412 /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2413 * to 0 can be aggregated to the resultant
2414 */
2417 {
2418 if( !SCIPisNegative(scip, obj) )
2419 {
2420 /* aggregate resultant to operand */
2421 SCIP_CALL( SCIPaggregateVars(scip, resvar, var, 1.0, -1.0, 0.0, &infeasible, &redundant,
2422 &aggregated) );
2423
2424 if( aggregated )
2425 {
2426 ++(*naggrvars);
2427
2428 linearize = TRUE;
2429
2430 /* delete redundant entry from constraint */
2431 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2432 ++(*nchgcoefs);
2433
2435 "dual aggregating operand <%s> with 1 up- and downlock to the resultant <%s> in constraint <%s>\n",
2436 SCIPvarGetName(var), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2437 }
2438
2439 *cutoff = *cutoff || infeasible;
2440 }
2441 else
2442 goodvarsfound = TRUE;
2443 }
2444 }
2445 assert(*nchgcoefs - oldnchgcoefs <= nvars);
2446
2447 /* if we aggregated an operands with the resultant we can also fix "good" independant operands to 1, since
2448 * the correctness of "resultant = 0 => at least one operand = 0" in enforced by that aggregation
2449 * without an aggregation we cannot fix these variables since it might lead to infeasibility, e.g.
2450 *
2451 * obj(x3) = -1
2452 * r = x1 * x2 * x3
2453 * r = 0
2454 * x1 = 1
2455 * x2 = 1
2456 */
2457 if( !*cutoff && goodvarsfound && linearize )
2458 {
2459 /* fix good variables to 1 */
2460 for( v = consdata->nvars - 1; v >= 0; --v )
2461 {
2462 var = vars[v];
2463 assert(var != NULL);
2464
2467 {
2468#ifndef NDEBUG
2469 /* aggregated objective value of active variable need to be negative */
2470 SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2471 assert(SCIPisNegative(scip, obj));
2472#endif
2474 "dual-fixing variable <%s> in constraint <%s> to 1, because the contribution is negative\n",
2475 SCIPvarGetName(var), SCIPconsGetName(cons));
2476
2477 SCIP_CALL( SCIPfixVar(scip, var, 1.0, &infeasible, &fixed) );
2478
2479 assert(!infeasible);
2480 if( fixed )
2481 ++(*nfixedvars);
2482 }
2483 }
2484 assert(*nfixedvars - oldnfixedvars <= consdata->nvars);
2485 }
2486 assert(*nchgcoefs - oldnchgcoefs + *nfixedvars - oldnfixedvars <= nvars);
2487 }
2488 /* if the downlocks of the resultant are only from this constraint and the objective contribution is positive,
2489 * we can try to fix operands
2490 */
2491 else if( SCIPvarGetNLocksDownType(resvar, SCIP_LOCKTYPE_MODEL) == 1 )
2492 {
2493 SCIP_Bool locksareone = TRUE;
2494 int maxpos = -1;
2495
2496 for( v = nvars - 1; v >= 0; --v )
2497 {
2498 var = vars[v];
2499 assert(var != NULL);
2502
2503 /* check if all resultants are only locked by this constraint */
2504 locksareone = locksareone && (SCIPvarGetNLocksUpType(var, SCIP_LOCKTYPE_MODEL) == 1
2506
2507 /* get aggregated objective value of active variable */
2508 SCIP_CALL( SCIPvarGetAggregatedObj(var, &obj) );
2509
2510 /* memorize maximal objective value of operands and its position */
2511 if( obj > maxobj )
2512 {
2513 maxpos = v;
2514 maxobj = obj;
2515 }
2516
2517 /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2518 * to 0, and the absolute value of the contribution of the resultant exceeds can be eliminated and
2519 * aggregated to the resultant
2520 */
2522 && SCIPvarGetNLocksDownType(var, SCIP_LOCKTYPE_MODEL) == 1 && SCIPisGE(scip, obj, 0.0) )
2523 {
2524 SCIPdebugMsg(scip, "dualfix operand <%s> in constraint <%s> to 0\n", SCIPvarGetName(var), SCIPconsGetName(cons));
2525
2526 SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
2527
2528 *cutoff = *cutoff || infeasible;
2529 if( fixed )
2530 ++(*nfixedvars);
2531
2532 zerofix = TRUE;
2533 }
2534 }
2535 assert(*nchgcoefs - oldnchgcoefs <= nvars);
2536
2537 /* if constraint is still active and all operands are only lock by this constraint, we check if we can fix
2538 * the worst (in objective contribution) operand to zero
2539 */
2540 if( !zerofix && locksareone && SCIPisGE(scip, resobj, REALABS(maxobj)) )
2541 {
2542 assert(!zerofix);
2543 /* objective contribution needs to be negative, otherwise, the variable should already be fixed to 0 */
2544 assert(SCIPisLT(scip, maxobj, 0.0));
2545
2546 SCIPdebugMsg(scip, "dualfix operand <%s> with worst contribution in constraint <%s> to 0\n", SCIPvarGetName(vars[maxpos]), SCIPconsGetName(cons));
2547
2548 SCIP_CALL( SCIPfixVar(scip, vars[maxpos], 0.0, &infeasible, &fixed) );
2549
2550 *cutoff = *cutoff || infeasible;
2551 if( fixed )
2552 ++(*nfixedvars);
2553
2554 zerofix = TRUE;
2555 }
2556
2557 /* fix the resultant if one operand was fixed to zero and delete the constraint */
2558 if( zerofix )
2559 {
2560 SCIPdebugMsg(scip, "fix resultant <%s> in constraint <%s> to 0\n", SCIPvarGetName(resvar), SCIPconsGetName(cons));
2561
2562 SCIP_CALL( SCIPfixVar(scip, resvar, 0.0, &infeasible, &fixed) );
2563
2564 *cutoff = *cutoff || infeasible;
2565 if( fixed )
2566 ++(*nfixedvars);
2567
2568 SCIPdebugMsg(scip, "deleting constraint <%s> because at least one operand and the resultant is fixed to zero\n", SCIPconsGetName(cons));
2569
2570 SCIP_CALL( SCIPdelCons(scip, cons) );
2571 ++(*ndelconss);
2572 }
2573 }
2574
2575 /* we have to linearize the constraint, otherwise we might get wrong propagations, since due to aggregations a
2576 * resultant fixed to zero is already fulfilling the constraint, and we must not ensure that some remaining
2577 * operand needs to be 0
2578 */
2579 if( linearize )
2580 {
2581 SCIP_CONS* newcons;
2582 char consname[SCIP_MAXSTRLEN];
2583 SCIP_VAR* consvars[2];
2584 SCIP_Real vals[2];
2585
2586 assert(SCIPconsIsActive(cons));
2587
2588 consvars[0] = consdata->resvar;
2589 vals[0] = 1.0;
2590 vals[1] = -1.0;
2591
2592 /* create operator linear constraints */
2593 for( v = consdata->nvars - 1; v >= 0; --v )
2594 {
2595 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
2596 consvars[1] = consdata->vars[v];
2597
2598 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, consvars, vals, -SCIPinfinity(scip), 0.0,
2602 SCIPconsIsStickingAtNode(cons)) );
2603
2604 /* add constraint */
2605 SCIP_CALL( SCIPaddCons(scip, newcons) );
2606 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
2607 }
2608 (*naddconss) += consdata->nvars;
2609
2610 SCIPdebugMsg(scip, "deleting constraint <%s> because it was linearized\n", SCIPconsGetName(cons));
2611
2612 SCIP_CALL( SCIPdelCons(scip, cons) );
2613 ++(*ndelconss);
2614 }
2615 /* if only one operand is leftover, aggregate it to the resultant */
2616 else if( consdata->nvars == 1 )
2617 {
2618 SCIPdebugMsg(scip, "aggregating last operand <%s> to the resultant <%s> in constraint <%s>\n", SCIPvarGetName(consdata->vars[0]), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2619
2620 /* aggregate resultant to operand */
2621 SCIP_CALL( SCIPaggregateVars(scip, resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2622 &infeasible, &redundant, &aggregated) );
2623
2624 if( aggregated )
2625 ++(*naggrvars);
2626
2627 *cutoff = *cutoff || infeasible;
2628
2629 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2630
2631 SCIP_CALL( SCIPdelCons(scip, cons) );
2632 ++(*ndelconss);
2633 }
2634
2635 /* if no operand is leftover delete the constraint */
2636 if( SCIPconsIsActive(cons) && consdata->nvars == 0 )
2637 {
2638 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2639
2640 SCIP_CALL( SCIPdelCons(scip, cons) );
2641 ++(*ndelconss);
2642 }
2643 }
2644 }
2645
2646 SCIPfreeBufferArray(scip, &impoperands);
2647
2648 return SCIP_OKAY;
2649}
2650
2651/** 1. check if at least two operands or one operand and the resultant are in one clique, if so, we can fix the
2652 * resultant to zero and in the former case we can also delete this constraint but we need to extract the clique
2653 * information as constraint
2654 *
2655 * x == AND(y, z) and clique(y,z) => x = 0, delete constraint and create y + z <= 1
2656 * x == AND(y, z) and clique(x,y) => x = 0
2657 *
2658 * special handled cases are:
2659 * - if the resultant is a negation of an operand, in that case we fix the resultant to 0
2660 * - if the resultant is equal to an operand, we will linearize this constraint by adding all necessary
2661 * set-packing constraints like resultant + ~operand <= 1 and delete the old constraint
2662 *
2663 * x == AND(~x, y) => x = 0
2664 * x == AND(x, y) => add x + ~y <= 1 and delete the constraint
2665 *
2666 * 2. check if one operand is in a clique with the negation of all other operands, this means we can aggregate this
2667 * operand to the resultant
2668 *
2669 * r == AND(x,y,z) and clique(x,~y) and clique(x,~z) => r == x
2670 *
2671 * 3. check if the resultant and the negations of all operands are in a clique
2672 *
2673 * r == AND(x,y) and clique(r, ~x,~y) => upgrade the constraint to a set-partitioning constraint r + ~x + ~y = 1
2674 *
2675 * @note We removed also fixed variables and propagate them, and if only one operand is remaining due to removal, we
2676 * will aggregate the resultant with this operand
2677 */
2678static
2680 SCIP* scip, /**< SCIP data structure */
2681 SCIP_CONS* cons, /**< constraint to process */
2682 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2683 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2684 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
2685 int* naggrvars, /**< pointer to add up the number of aggregated variables */
2686 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
2687 int* ndelconss, /**< pointer to add up the number of deleted constraints */
2688 int* naddconss /**< pointer to add up the number of added constraints */
2689 )
2690{
2691 SCIP_CONSDATA* consdata;
2692 SCIP_VAR** vars;
2693 SCIP_VAR* var1;
2694 SCIP_VAR* var2;
2695 int nvars;
2696 int vstart;
2697 int vend;
2698 int v;
2699 int v2;
2700 SCIP_Bool negated;
2701 SCIP_Bool value1;
2702 SCIP_Bool value2;
2703 SCIP_Bool infeasible;
2704 SCIP_Bool fixed;
2705 SCIP_Bool allnegoperandsexist;
2706
2707 assert(scip != NULL);
2708 assert(cons != NULL);
2709 assert(eventhdlr != NULL);
2710 assert(cutoff != NULL);
2711 assert(nfixedvars != NULL);
2712 assert(naggrvars != NULL);
2713 assert(nchgcoefs != NULL);
2714 assert(ndelconss != NULL);
2715 assert(naddconss != NULL);
2716
2717 consdata = SCIPconsGetData(cons);
2718 assert(consdata != NULL);
2719
2720 if( !SCIPconsIsActive(cons) || SCIPconsIsModifiable(cons) )
2721 return SCIP_OKAY;
2722
2723 vars = consdata->vars;
2724 nvars = consdata->nvars;
2725 assert(vars != NULL || nvars == 0);
2726
2727 /* remove fixed variables to be able to ask for cliques
2728 *
2729 * if an operand is fixed to 0 fix the resultant to 0 and delete the constraint
2730 * if an operand is fixed to 1 remove it from the constraint
2731 */
2732 for( v = nvars - 1; v >= 0; --v )
2733 {
2734 assert(vars != NULL);
2735
2736 if( SCIPvarGetLbGlobal(vars[v]) > 0.5 )
2737 {
2738 SCIPdebugMsg(scip, "In constraint <%s> the operand <%s> is fixed to 1 so remove it from the constraint\n",
2739 SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
2740
2741 /* because we loop from back to front we can delete the entry in the consdata structure */
2742 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2743 ++(*nchgcoefs);
2744
2745 assert(consdata->vars == vars);
2746
2747 continue;
2748 }
2749 else if( SCIPvarGetUbGlobal(vars[v]) < 0.5 )
2750 {
2751 SCIPdebugMsg(scip, "constraint <%s> redundant: because operand <%s> is fixed to zero so we can fix the resultant <%s> to 0\n",
2752 SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
2753
2754 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2755 *cutoff = *cutoff || infeasible;
2756 if( fixed )
2757 ++(*nfixedvars);
2758
2759 SCIP_CALL( SCIPdelCons(scip, cons) );
2760 ++(*ndelconss);
2761
2762 return SCIP_OKAY;
2763 }
2764 }
2765
2766 /* if we deleted some operands constraint might be redundant */
2767 if( consdata->nvars < nvars )
2768 {
2769 assert(vars == consdata->vars);
2770
2771 /* all operands fixed to one were removed, so if no operand is left this means we can fix the resultant to 1
2772 * too
2773 */
2774 if( consdata->nvars == 0 )
2775 {
2776 SCIPdebugMsg(scip, "All operand in constraint <%s> were deleted, so the resultant needs to be fixed to 1\n",
2777 SCIPconsGetName(cons));
2778
2779 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 1.0, &infeasible, &fixed) );
2780 *cutoff = *cutoff || infeasible;
2781 if( fixed )
2782 ++(*nfixedvars);
2783
2784 SCIP_CALL( SCIPdelCons(scip, cons) );
2785 ++(*ndelconss);
2786
2787 return SCIP_OKAY;
2788 }
2789 /* if only one not fixed operand is left, we can aggregate it to the resultant */
2790 else if( consdata->nvars == 1 )
2791 {
2792 SCIP_Bool redundant;
2793 SCIP_Bool aggregated;
2794
2795 /* aggregate resultant to last operand */
2796 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2797 &infeasible, &redundant, &aggregated) );
2798
2799 if( aggregated )
2800 ++(*naggrvars);
2801
2802 SCIP_CALL( SCIPdelCons(scip, cons) );
2803 ++(*ndelconss);
2804
2805 *cutoff = *cutoff || infeasible;
2806
2807 return SCIP_OKAY;
2808 }
2809
2810 nvars = consdata->nvars;
2811 }
2812
2813 /* @todo when cliques are improved, we only need to collect all clique-ids for all variables and check for doubled
2814 * entries
2815 */
2816 /* case 1 first part */
2817 /* check if two operands are in a clique */
2818 for( v = nvars - 1; v > 0; --v )
2819 {
2820 assert(vars != NULL);
2821
2822 var1 = vars[v];
2823 assert(var1 != NULL);
2824 negated = FALSE;
2825
2826 SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
2827 assert(var1 != NULL);
2828
2829 if( negated )
2830 value1 = FALSE;
2831 else
2832 value1 = TRUE;
2833
2834 assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
2835
2836 for( v2 = v - 1; v2 >= 0; --v2 )
2837 {
2838 var2 = vars[v2];
2839 assert(var2 != NULL);
2840
2841 negated = FALSE;
2842 SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
2843 assert(var2 != NULL);
2844
2845 if( negated )
2846 value2 = FALSE;
2847 else
2848 value2 = TRUE;
2849
2850 assert(SCIPvarGetStatus(var2) != SCIP_VARSTATUS_FIXED);
2851
2852 /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2853 * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better
2854 * continue
2855 */
2856 if( var1 == var2 )
2857 continue;
2858
2859 if( SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
2860 {
2861 SCIP_CONS* cliquecons;
2862 SCIP_VAR* consvars[2];
2863 char name[SCIP_MAXSTRLEN];
2864
2865 SCIPdebugMsg(scip, "constraint <%s> redundant: because variable <%s> and variable <%s> are in a clique, the resultant <%s> can be fixed to 0\n",
2866 SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2), SCIPvarGetName(consdata->resvar));
2867
2868 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2869 *cutoff = *cutoff || infeasible;
2870 if( fixed )
2871 ++(*nfixedvars);
2872
2873 /* create clique constraint which lead to the last fixing */
2874 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%d", SCIPconsGetName(cons), v2);
2875
2876 if( value1 )
2877 consvars[0] = var1;
2878 else
2879 {
2880 SCIP_CALL( SCIPgetNegatedVar(scip, var1, &(consvars[0])) );
2881 }
2882
2883 if( value2 )
2884 consvars[1] = var2;
2885 else
2886 {
2887 SCIP_CALL( SCIPgetNegatedVar(scip, var2, &(consvars[1])) );
2888 }
2889
2890 SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
2892 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2894 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
2895 SCIPdebugMsg(scip, " -> adding clique constraint: ");
2896 SCIPdebugPrintCons(scip, cliquecons, NULL);
2897 SCIP_CALL( SCIPaddCons(scip, cliquecons) );
2898 SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
2899 ++(*naddconss);
2900
2901 SCIP_CALL( SCIPdelCons(scip, cons) );
2902 ++(*ndelconss);
2903
2904 return SCIP_OKAY;
2905 }
2906 }
2907 }
2908
2909 var1 = consdata->resvar;
2910 assert(var1 != NULL);
2911
2912 negated = FALSE;
2913 SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
2914 assert(var1 != NULL);
2915
2916 /* it may appear that we have a fixed resultant */
2918 {
2919 /* resultant is fixed to 1, so fix all operands to 1 */
2920 if( SCIPvarGetLbGlobal(consdata->resvar) > 0.5 )
2921 {
2922 SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> is fixed to 1 so fix all operands to 1\n",
2923 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2924
2925 /* fix all operands to 1 */
2926 for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2927 {
2928 assert(vars != NULL);
2929
2930 SCIPdebugMsg(scip, "Fixing operand <%s> to 1.\n", SCIPvarGetName(vars[v]));
2931
2932 SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2933 *cutoff = *cutoff || infeasible;
2934
2935 if( fixed )
2936 ++(*nfixedvars);
2937 }
2938
2939 SCIP_CALL( SCIPdelCons(scip, cons) );
2940 ++(*ndelconss);
2941 }
2942 /* the upgrade to a linear constraint because of the to 0 fixed resultant we do in propagateCons() */
2943 else
2944 assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
2945
2946 return SCIP_OKAY;
2947 }
2948
2949 if( negated )
2950 value1 = FALSE;
2951 else
2952 value1 = TRUE;
2953
2954 /* case 1 second part */
2955 /* check if one operands is in a clique with the resultant */
2956 for( v = nvars - 1; v >= 0; --v )
2957 {
2958 assert(vars != NULL);
2959
2960 var2 = vars[v];
2961 assert(var2 != NULL);
2962
2963 negated = FALSE;
2964 SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
2965 assert(var2 != NULL);
2966
2967 if( negated )
2968 value2 = FALSE;
2969 else
2970 value2 = TRUE;
2971
2972 /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2973 * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better continue
2974 */
2975 if( var1 == var2 )
2976 {
2977 /* x1 == AND(~x1, x2 ...) => x1 = 0 */
2978 if( value1 != value2 )
2979 {
2980 SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
2981 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2982
2983 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2984 *cutoff = *cutoff || infeasible;
2985
2986 if( fixed )
2987 ++(*nfixedvars);
2988
2989 return SCIP_OKAY;
2990 }
2991 /* x1 == AND(x1, x2 ...) => delete constraint and create all set-packing constraints x1 + ~x2 <= 1, x1 + ~... <= 1 */
2992 else
2993 {
2994 SCIP_CONS* cliquecons;
2995 SCIP_VAR* consvars[2];
2996 char name[SCIP_MAXSTRLEN];
2997
2998 assert(value1 == value2);
2999
3000 consvars[0] = consdata->resvar;
3001
3002 for( v2 = nvars - 1; v2 >= 0; --v2 )
3003 {
3004 var2 = vars[v2];
3005 negated = FALSE;
3006 SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
3007
3008 /* if the active representations of the resultant and an operand are different then we need to extract
3009 * this as a clique constraint
3010 *
3011 * if the active representations of the resultant and an operand are equal then the clique constraint
3012 * would look like x1 + ~x1 <= 1, which is redundant
3013 *
3014 * if the active representations of the resultant and an operand are negated of each other then the
3015 * clique constraint would look like x1 + x1 <= 1, which will lead to a fixation of the resultant later
3016 * on
3017 */
3018 if( var1 == var2 )
3019 {
3020 if( value1 == negated )
3021 {
3022 SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
3023 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
3024
3025 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3026 *cutoff = *cutoff || infeasible;
3027
3028 if( fixed )
3029 ++(*nfixedvars);
3030
3031 break;
3032 }
3033 }
3034 else
3035 {
3036 SCIP_CALL( SCIPgetNegatedVar(scip, vars[v2], &consvars[1]) );
3037 assert(consvars[1] != NULL);
3038
3039 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%d", SCIPconsGetName(cons), v2);
3040
3041 SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
3043 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3045 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3046 SCIPdebugMsg(scip, " -> adding clique constraint: ");
3047 SCIPdebugPrintCons(scip, cliquecons, NULL);
3048 SCIP_CALL( SCIPaddCons(scip, cliquecons) );
3049 SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
3050 ++(*naddconss);
3051 }
3052 }
3053
3054 /* delete old constraint */
3055 SCIP_CALL( SCIPdelCons(scip, cons) );
3056 ++(*ndelconss);
3057
3058 return SCIP_OKAY;
3059 }
3060 }
3061
3062 /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
3063 * it explicitly
3064 */
3065 if( var1 == var2 && value1 == value2 )
3066 continue;
3067
3068 /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
3069 * handle it explicitly
3070 */
3071 if( (var1 == var2 && value1 != value2) || SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
3072 {
3073 SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because it is in a clique with operand <%s>\n",
3074 SCIPconsGetName(cons), SCIPvarGetName(var1), SCIPvarGetName(var2));
3075
3076 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3077 *cutoff = *cutoff || infeasible;
3078 if( fixed )
3079 ++(*nfixedvars);
3080
3081 return SCIP_OKAY;
3082 }
3083 }
3084
3085 if( !SCIPconsIsActive(cons) )
3086 return SCIP_OKAY;
3087
3088 v2 = -1;
3089 /* check which operands have a negated variable */
3090 for( v = nvars - 1; v >= 0; --v )
3091 {
3092 assert(vars != NULL);
3093
3094 var1 = vars[v];
3095 assert(var1 != NULL);
3096
3097 negated = FALSE;
3098 SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
3099 assert(var1 != NULL);
3100
3101 if( SCIPvarGetNegatedVar(var1) == NULL )
3102 {
3103 if( v2 >= 0 )
3104 break;
3105 v2 = v;
3106 }
3107 }
3108
3109 allnegoperandsexist = FALSE;
3110
3111 /* all operands have a negated variable, so we will check for all possible negated ciques */
3112 if( v2 == -1 )
3113 {
3114 allnegoperandsexist = TRUE;
3115 vstart = nvars - 1;
3116 vend = 0;
3117 }
3118 /* exactly one operands has no negated variable, so only this variable can be in a clique with all other negations */
3119 else if( v2 >= 0 && v == -1 )
3120 {
3121 vstart = v2;
3122 vend = v2;
3123 }
3124 /* at least two operands have no negated variable, so there is no possible clique with negated variables */
3125 else
3126 {
3127 vstart = -1;
3128 vend = 0;
3129 }
3130
3131 /* case 2 */
3132 /* check for negated cliques in the operands */
3133 for( v = vstart; v >= vend; --v )
3134 {
3135 assert(vars != NULL);
3136
3137 var1 = vars[v];
3138 assert(var1 != NULL);
3139
3140 negated = FALSE;
3141 SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negated) );
3142 assert(var1 != NULL);
3143
3144 if( negated )
3145 value1 = FALSE;
3146 else
3147 value1 = TRUE;
3148
3149 for( v2 = nvars - 1; v2 >= 0; --v2 )
3150 {
3151 if( v2 == v )
3152 continue;
3153
3154 var2 = vars[v2];
3155 assert(var2 != NULL);
3156
3157 negated = FALSE;
3158 SCIP_CALL( SCIPvarGetProbvarBinary(&var2, &negated) );
3159 assert(var2 != NULL);
3160
3161 if( negated )
3162 value2 = FALSE;
3163 else
3164 value2 = TRUE;
3165
3166 assert(SCIPvarGetNegatedVar(var2) != NULL);
3167
3168 /* invert flag, because we want to check var 1 against all negations of the other variables */
3169 value2 = !value2;
3170
3171 /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
3172 * it explicitly
3173 */
3174 if( var1 == var2 && value1 == value2 )
3175 {
3176 SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because two operands are negated of each other\n",
3177 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
3178
3179 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3180 *cutoff = *cutoff || infeasible;
3181 if( fixed )
3182 ++(*nfixedvars);
3183
3184 return SCIP_OKAY;
3185 }
3186
3187 /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
3188 * handle it explicitly
3189 */
3190 if( var1 == var2 && value1 != value2 )
3191 continue;
3192
3193 if( !SCIPvarsHaveCommonClique(var1, value1, var2, value2, TRUE) )
3194 break;
3195 }
3196
3197 if( v2 == -1 )
3198 {
3199 SCIP_Bool redundant;
3200 SCIP_Bool aggregated;
3201
3202 SCIPdebugMsg(scip, "In constraint <%s> the operand <%s> is in a negated clique with all other operands, so we can aggregated this operand to the resultant <%s>.\n",
3203 SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
3204
3205 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, vars[v], 1.0, -1.0, 0.0,
3206 &infeasible, &redundant, &aggregated) );
3207 *cutoff = *cutoff || infeasible;
3208
3209 if( aggregated )
3210 ++(*naggrvars);
3211
3212 return SCIP_OKAY;
3213 }
3214 }
3215
3216 /* case 3 */
3217 /* check if the resultant and the negations of the operands are in a clique, then we can upgrade this constraint to a
3218 * set-partitioning constraint
3219 */
3220 if( allnegoperandsexist && SCIPconsIsActive(cons) )
3221 {
3222 SCIP_VAR** newvars;
3223 SCIP_Bool* negations;
3224 SCIP_Bool upgrade;
3225
3226 SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars + 1) );
3227 SCIP_CALL( SCIPallocBufferArray(scip, &negations, nvars + 1) );
3228 BMSclearMemoryArray(negations, nvars + 1);
3229
3230 var1 = consdata->resvar;
3231 SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negations[nvars]) );
3232 assert(var1 != NULL);
3233 assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
3234
3235 newvars[nvars] = var1;
3236
3237 /* get active variables */
3238 for( v = nvars - 1; v >= 0; --v )
3239 {
3240 assert(vars != NULL);
3241
3242 var1 = vars[v];
3243 SCIP_CALL( SCIPvarGetProbvarBinary(&var1, &negations[v]) );
3244 assert(var1 != NULL);
3245 assert(SCIPvarGetStatus(var1) != SCIP_VARSTATUS_FIXED);
3246
3247 newvars[v] = var1;
3248
3249 /* there should be no variable left that is equal or negated to the resultant */
3250 assert(newvars[v] != newvars[nvars]);
3251 }
3252
3253 upgrade = TRUE;
3254
3255 /* the resultant is in a clique with the negations of all operands, due to this AND-constraint */
3256 /* only check if the negations of all operands are in a clique */
3257 for( v = nvars - 1; v >= 0 && upgrade; --v )
3258 {
3259 for( v2 = v - 1; v2 >= 0; --v2 )
3260 {
3261 /* the resultant need to be in a clique with the negations of all operands */
3262 if( !SCIPvarsHaveCommonClique(newvars[v], negations[v], newvars[v2], negations[v2], TRUE) )
3263 {
3264 upgrade = FALSE;
3265 break;
3266 }
3267 }
3268 }
3269
3270 /* all variables are in a clique, so upgrade thi AND-constraint */
3271 if( upgrade )
3272 {
3273 SCIP_CONS* cliquecons;
3274 char name[SCIP_MAXSTRLEN];
3275
3276 /* get new constraint variables */
3277 if( negations[nvars] )
3278 {
3279 /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3280 * (e.g. resultant = ~x = 1 - x and x = y = newvars[nvars] and negations[nvars] = TRUE,
3281 * then y does not need to have a negated variable, yet)
3282 */
3283 SCIP_CALL( SCIPgetNegatedVar(scip, newvars[nvars], &(newvars[nvars])) );
3284 }
3285 assert(newvars[nvars] != NULL);
3286
3287 for( v = nvars - 1; v >= 0; --v )
3288 {
3289 if( !negations[v] )
3290 {
3291 /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3292 * (e.g. vars[v] = ~x = 1 - x and x = y = newvars[v] and negations[v] = TRUE,
3293 * then y does not need to have a negated variable, yet)
3294 */
3295 SCIP_CALL( SCIPgetNegatedVar(scip, newvars[v], &(newvars[v])) );
3296 }
3297 assert(newvars[v] != NULL);
3298 }
3299
3300 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clqeq", SCIPconsGetName(cons));
3301
3302 SCIP_CALL( SCIPcreateConsSetpart(scip, &cliquecons, name, nvars + 1, newvars,
3304 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3306 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3307 SCIPdebugMsg(scip, " -> upgrading AND-constraint <%s> with use of clique information to a set-partitioning constraint: \n", SCIPconsGetName(cons));
3308 SCIPdebugPrintCons(scip, cliquecons, NULL);
3309 SCIP_CALL( SCIPaddCons(scip, cliquecons) );
3310 SCIP_CALL( SCIPreleaseCons(scip, &cliquecons) );
3311 ++(*naddconss);
3312
3313 /* delete old constraint */
3314 SCIP_CALL( SCIPdelCons(scip, cons) );
3315 ++(*ndelconss);
3316 }
3317
3318 SCIPfreeBufferArray(scip, &negations);
3319 SCIPfreeBufferArray(scip, &newvars);
3320 }
3321
3322 return SCIP_OKAY;
3323}
3324
3325/** gets the key of the given element */
3326static
3327SCIP_DECL_HASHGETKEY(hashGetKeyAndcons)
3328{ /*lint --e{715}*/
3329 /* the key is the element itself */
3330 return elem;
3331}
3332
3333/** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
3334static
3335SCIP_DECL_HASHKEYEQ(hashKeyEqAndcons)
3336{
3337 SCIP_CONSDATA* consdata1;
3338 SCIP_CONSDATA* consdata2;
3339 SCIP_Bool coefsequal;
3340 int i;
3341#ifndef NDEBUG
3342 SCIP* scip;
3343
3344 scip = (SCIP*)userptr;
3345 assert(scip != NULL);
3346#endif
3347
3348 consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
3349 consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
3350
3351 /* checks trivial case */
3352 if( consdata1->nvars != consdata2->nvars )
3353 return FALSE;
3354
3355 /* sorts the constraints */
3356 consdataSort(consdata1);
3357 consdataSort(consdata2);
3358 assert(consdata1->sorted);
3359 assert(consdata2->sorted);
3360
3361 coefsequal = TRUE;
3362
3363 for( i = 0; i < consdata1->nvars ; ++i )
3364 {
3365 /* tests if variables are equal */
3366 if( consdata1->vars[i] != consdata2->vars[i] )
3367 {
3368 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
3369 SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
3370 coefsequal = FALSE;
3371 break;
3372 }
3373 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
3374 }
3375
3376 return coefsequal;
3377}
3378
3379/** returns the hash value of the key */
3380static
3381SCIP_DECL_HASHKEYVAL(hashKeyValAndcons)
3382{ /*lint --e{715}*/
3383 SCIP_CONSDATA* consdata;
3384 int minidx;
3385 int mididx;
3386 int maxidx;
3387
3388 consdata = SCIPconsGetData((SCIP_CONS*)key);
3389 assert(consdata != NULL);
3390 assert(consdata->sorted);
3391 assert(consdata->nvars > 0);
3392
3393 minidx = SCIPvarGetIndex(consdata->vars[0]);
3394 mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
3395 maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
3396 assert(minidx >= 0 && minidx <= maxidx);
3397
3398 return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
3399}
3400
3401/** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3402 * accordingly; in contrast to removeRedundantConstraints(), it uses a hash table
3403 */
3404static
3406 SCIP* scip, /**< SCIP data structure */
3407 BMS_BLKMEM* blkmem, /**< block memory */
3408 SCIP_CONS** conss, /**< constraint set */
3409 int nconss, /**< number of constraints in constraint set */
3410 int* firstchange, /**< pointer to store first changed constraint */
3411 SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3412 int* naggrvars, /**< pointer to count number of aggregated variables */
3413 int* ndelconss /**< pointer to count number of deleted constraints */
3414 )
3415{
3416 SCIP_HASHTABLE* hashtable;
3417 int hashtablesize;
3418 int c;
3419
3420 assert(conss != NULL);
3421 assert(ndelconss != NULL);
3422
3423 /* create a hash table for the constraint set */
3424 hashtablesize = nconss;
3425 hashtablesize = MAX(hashtablesize, HASHSIZE_ANDCONS);
3426 SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3427 hashGetKeyAndcons, hashKeyEqAndcons, hashKeyValAndcons, (void*) scip) );
3428
3429 *cutoff = FALSE;
3430
3431 /* check all constraints in the given set for redundancy */
3432 for( c = 0; c < nconss; ++c )
3433 {
3434 SCIP_CONS* cons0;
3435 SCIP_CONS* cons1;
3436 SCIP_CONSDATA* consdata0;
3437
3438 cons0 = conss[c];
3439
3440 if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
3441 continue;
3442
3443 consdata0 = SCIPconsGetData(cons0);
3444
3445 /* sort the constraint */
3446 consdataSort(consdata0);
3447 assert(consdata0->sorted);
3448
3449 /* get constraint from current hash table with same variables as cons0 */
3450 cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3451
3452 if( cons1 != NULL )
3453 {
3454 SCIP_CONSDATA* consdata1;
3455 SCIP_Bool redundant;
3456
3457 assert(SCIPconsIsActive(cons1));
3458 assert(!SCIPconsIsModifiable(cons1));
3459
3460 consdata1 = SCIPconsGetData(cons1);
3461
3462 assert(consdata1 != NULL);
3463 assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3464
3465 assert(consdata0->sorted && consdata1->sorted);
3466 assert(consdata0->vars[0] == consdata1->vars[0]);
3467
3468 redundant = FALSE;
3469
3470 if( consdata0->resvar != consdata1->resvar )
3471 {
3472 SCIP_Bool aggregated;
3473
3474 assert(SCIPvarCompare(consdata0->resvar, consdata1->resvar) != 0);
3475
3476 /* aggregate resultants */
3477 SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3478 cutoff, &redundant, &aggregated) );
3479 assert(redundant || SCIPdoNotAggr(scip));
3480
3481 if( aggregated )
3482 ++(*naggrvars);
3483 if( *cutoff )
3484 goto TERMINATE;
3485 }
3486 else
3487 redundant = TRUE;
3488
3489 /* delete consdel */
3490 if( redundant )
3491 {
3492 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3493 /* coverity[swapped_arguments] */
3494 SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
3495
3496 /* also take the check when upgrade flag over if necessary */
3497 consdata1->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3498 consdata1->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3499
3500 SCIP_CALL( SCIPdelCons(scip, cons0) );
3501 (*ndelconss)++;
3502 }
3503
3504 /* update the first changed constraint to begin the next aggregation round with */
3505 if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3506 *firstchange = SCIPconsGetPos(cons1);
3507
3508 assert(SCIPconsIsActive(cons1));
3509 }
3510 else
3511 {
3512 /* no such constraint in current hash table: insert cons0 into hash table */
3513 SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3514 }
3515 }
3516 TERMINATE:
3517 /* free hash table */
3518 SCIPhashtableFree(&hashtable);
3519
3520 return SCIP_OKAY;
3521}
3522
3523/** helper function to enforce constraints */
3524static
3526 SCIP* scip, /**< SCIP data structure */
3527 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3528 SCIP_CONS** conss, /**< constraints to process */
3529 int nconss, /**< number of constraints */
3530 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
3531 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
3532 )
3533{
3534 SCIP_CONSHDLRDATA* conshdlrdata;
3535 SCIP_Bool separated;
3536 SCIP_Bool violated;
3537 SCIP_Bool cutoff;
3538 int i;
3539
3540 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3541 assert(conshdlrdata != NULL);
3542
3543 *result = SCIP_FEASIBLE;
3544
3545 /* method is called only for integral solutions, because the enforcing priority is negative */
3546 for( i = 0; i < nconss; i++ )
3547 {
3548 SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
3549 if( !violated )
3550 continue;
3551
3552 if( !conshdlrdata->enforcecuts )
3553 {
3554 *result = SCIP_INFEASIBLE;
3555 return SCIP_OKAY;
3556 }
3557
3558 SCIP_CALL( separateCons(scip, conss[i], sol, &separated, &cutoff) );
3559 if( cutoff )
3560 {
3561 *result = SCIP_CUTOFF;
3562 return SCIP_OKAY;
3563 }
3564 else if( separated )
3565 {
3566 *result = SCIP_SEPARATED;
3567 }
3568 else if( *result == SCIP_FEASIBLE ) /* do not change result separated to infeasible */
3569 {
3570 *result = SCIP_INFEASIBLE;
3571 }
3572 }
3573
3574 return SCIP_OKAY;
3575}
3576
3577
3578/** compares constraint with all prior constraints for possible redundancy or aggregation,
3579 * and removes or changes constraint accordingly
3580 */
3581static
3583 SCIP* scip, /**< SCIP data structure */
3584 SCIP_CONS** conss, /**< constraint set */
3585 int firstchange, /**< first constraint that changed since last pair preprocessing round */
3586 int chkind, /**< index of constraint to check against all prior indices upto startind */
3587 SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3588 int* naggrvars, /**< pointer to count number of aggregated variables */
3589 int* nbdchgs, /**< pointer to count the number of performed bound changes, or NULL */
3590 int* ndelconss /**< pointer to count number of deleted constraints */
3591 )
3592{
3593 SCIP_CONS* cons0;
3594 SCIP_CONSDATA* consdata0;
3595 SCIP_Bool cons0changed;
3596 int c;
3597
3598 assert(conss != NULL);
3599 assert(firstchange <= chkind);
3600 assert(cutoff != NULL);
3601 assert(naggrvars != NULL);
3602 assert(nbdchgs != NULL);
3603 assert(ndelconss != NULL);
3604
3605 /* get the constraint to be checked against all prior constraints */
3606 cons0 = conss[chkind];
3607 assert(SCIPconsIsActive(cons0));
3608 assert(!SCIPconsIsModifiable(cons0));
3609
3610 consdata0 = SCIPconsGetData(cons0);
3611
3612 /* sort the constraint */
3613 consdataSort(consdata0);
3614
3615 assert(consdata0->nvars >= 1);
3616 assert(consdata0->sorted);
3617
3618 /* check constraint against all prior constraints */
3619 cons0changed = consdata0->changed;
3620
3621 if( SCIPconsIsActive(cons0) )
3622 {
3623 for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff); ++c )
3624 {
3625 SCIP_CONS* cons1;
3626 SCIP_CONSDATA* consdata1;
3627 SCIP_Bool cons0superset;
3628 SCIP_Bool cons1superset;
3629 int v0;
3630 int v1;
3631
3632 if( c % 1000 == 0 && SCIPisStopped(scip) )
3633 break;
3634
3635 cons1 = conss[c];
3636
3637 /* ignore inactive and modifiable constraints */
3638 if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
3639 continue;
3640
3641 consdata1 = SCIPconsGetData(cons1);
3642 assert(consdata1 != NULL);
3643
3644#ifdef SCIP_DISABLED_CODE
3645 SCIPdebugMsg(scip, "preprocess AND-constraint pair <%s>[chg:%d] and <%s>[chg:%d]\n",
3646 SCIPconsGetName(cons0), cons0changed, SCIPconsGetName(cons1), consdata1->changed);
3647#endif
3648
3649 /* if both constraints were not changed since last round, we can ignore the pair */
3650 if( !cons0changed && !consdata1->changed )
3651 continue;
3652
3653 assert(consdata1->nvars >= 1);
3654
3655 /* sort the constraint */
3656 consdataSort(consdata1);
3657 assert(consdata1->sorted);
3658
3659 /* check consdata0 against consdata1:
3660 * - if they consist of the same operands, the resultants can be aggregated
3661 * - if one operand list is a subset of the other, add implication r0 = 1 -> r1 = 1, or r1 = 1 -> r0 = 1
3662 */
3663 v0 = 0;
3664 v1 = 0;
3665 cons0superset = TRUE;
3666 cons1superset = TRUE;
3667 while( (v0 < consdata0->nvars || v1 < consdata1->nvars) && (cons0superset || cons1superset) )
3668 {
3669 int varcmp;
3670
3671 /* test, if variable appears in only one or in both constraints */
3672 if( v0 < consdata0->nvars && v1 < consdata1->nvars )
3673 varcmp = SCIPvarCompare(consdata0->vars[v0], consdata1->vars[v1]);
3674 else if( v0 < consdata0->nvars )
3675 varcmp = -1;
3676 else
3677 varcmp = +1;
3678
3679 switch( varcmp )
3680 {
3681 case -1:
3682 /* variable doesn't appear in consdata1 */
3683 cons1superset = FALSE;
3684 v0++;
3685 break;
3686
3687 case +1:
3688 /* variable doesn't appear in consdata0 */
3689 cons0superset = FALSE;
3690 v1++;
3691 break;
3692
3693 case 0:
3694 /* variable appears in both constraints */
3695 v0++;
3696 v1++;
3697 break;
3698
3699 default:
3700 SCIPerrorMessage("invalid comparison result\n");
3701 SCIPABORT();
3702 return SCIP_INVALIDDATA; /*lint !e527*/
3703 }
3704 }
3705
3706 /* check for equivalence and domination */
3707 if( cons0superset && cons1superset )
3708 {
3709 SCIP_Bool infeasible;
3710 SCIP_Bool redundant;
3711 SCIP_Bool aggregated;
3712
3713 /* constraints are equivalent */
3714 SCIPdebugMsg(scip, "equivalent AND-constraints <%s> and <%s>: aggregate resultants <%s> == <%s>\n",
3715 SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3716 SCIPvarGetName(consdata1->resvar));
3717
3718 /* aggregate resultants */
3719 SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3720 &infeasible, &redundant, &aggregated) );
3721 assert(redundant || SCIPdoNotAggr(scip));
3722
3723 if( aggregated )
3724 {
3725 assert(redundant);
3726 (*naggrvars)++;
3727 }
3728
3729 if( redundant )
3730 {
3731 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3732 SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
3733
3734 /* also take the check when upgrade flag over if necessary */
3735 consdata0->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3736 consdata0->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3737
3738 /* delete constraint */
3739 SCIP_CALL( SCIPdelCons(scip, cons1) );
3740 (*ndelconss)++;
3741 }
3742
3743 *cutoff = *cutoff || infeasible;
3744 }
3745 else if( cons0superset )
3746 {
3747 SCIP_Bool infeasible;
3748 int nboundchgs;
3749
3750 /* the conjunction of cons0 is a superset of the conjunction of cons1 */
3751 SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3752 SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPvarGetName(consdata0->resvar),
3753 SCIPvarGetName(consdata1->resvar));
3754
3755 /* add implication */
3756 SCIP_CALL( SCIPaddVarImplication(scip, consdata0->resvar, TRUE, consdata1->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3757 &infeasible, &nboundchgs) );
3758 *cutoff = *cutoff || infeasible;
3759 (*nbdchgs) += nboundchgs;
3760 }
3761 else if( cons1superset )
3762 {
3763 SCIP_Bool infeasible;
3764 int nboundchgs;
3765
3766 /* the conjunction of cons1 is a superset of the conjunction of cons0 */
3767 SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3768 SCIPconsGetName(cons1), SCIPconsGetName(cons0), SCIPvarGetName(consdata1->resvar),
3769 SCIPvarGetName(consdata0->resvar));
3770
3771 /* add implication */
3772 SCIP_CALL( SCIPaddVarImplication(scip, consdata1->resvar, TRUE, consdata0->resvar, SCIP_BOUNDTYPE_LOWER, 1.0,
3773 &infeasible, &nboundchgs) );
3774 *cutoff = *cutoff || infeasible;
3775 (*nbdchgs) += nboundchgs;
3776 }
3777 }
3778 }
3779 consdata0->changed = FALSE;
3780
3781 return SCIP_OKAY;
3782}
3783
3784/** adds symmetry information of constraint to a symmetry detection graph */
3785static
3787 SCIP* scip, /**< SCIP pointer */
3788 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */
3789 SCIP_CONS* cons, /**< constraint */
3790 SYM_GRAPH* graph, /**< symmetry detection graph */
3791 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */
3792 )
3793{
3794 SCIP_CONSDATA* consdata;
3795 SCIP_VAR** andvars;
3796 SCIP_VAR** vars;
3797 SCIP_Real* vals;
3798 SCIP_Real constant = 0.0;
3799 int nlocvars;
3800 int nvars;
3801 int i;
3802
3803 assert(scip != NULL);
3804 assert(cons != NULL);
3805 assert(graph != NULL);
3806 assert(success != NULL);
3807
3808 consdata = SCIPconsGetData(cons);
3809 assert(consdata != NULL);
3810
3811 /* get active variables of the constraint */
3812 nvars = SCIPgetNVars(scip);
3813 nlocvars = SCIPgetNVarsAnd(scip, cons);
3814
3815 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
3816 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
3817
3818 andvars = SCIPgetVarsAnd(scip, cons);
3819 for( i = 0; i < consdata->nvars; ++i )
3820 {
3821 vars[i] = andvars[i];
3822 vals[i] = 1.0;
3823 }
3824
3825 assert(SCIPgetResultantAnd(scip, cons) != NULL);
3826 vars[nlocvars] = SCIPgetResultantAnd(scip, cons);
3827 vals[nlocvars++] = 2.0;
3828 assert(nlocvars <= nvars);
3829
3830 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
3831
3833 nlocvars, cons, constant, constant, success) );
3834
3835 SCIPfreeBufferArray(scip, &vals);
3836 SCIPfreeBufferArray(scip, &vars);
3837
3838 return SCIP_OKAY;
3839}
3840
3841/*
3842 * Callback methods of constraint handler
3843 */
3844
3845/** copy method for constraint handler plugins (called when SCIP copies plugins) */
3846static
3848{ /*lint --e{715}*/
3849 assert(scip != NULL);
3850 assert(conshdlr != NULL);
3851 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
3852
3853 /* call inclusion method of constraint handler */
3855
3856 *valid = TRUE;
3857
3858 return SCIP_OKAY;
3859}
3860
3861/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3862static
3864{ /*lint --e{715}*/
3865 SCIP_CONSHDLRDATA* conshdlrdata;
3866
3867 /* free constraint handler data */
3868 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3869 assert(conshdlrdata != NULL);
3870
3871 conshdlrdataFree(scip, &conshdlrdata);
3872
3873 SCIPconshdlrSetData(conshdlr, NULL);
3874
3875 return SCIP_OKAY;
3876}
3877
3878
3879/** presolving initialization method of constraint handler (called when presolving is about to begin) */
3880static
3882{ /*lint --e{715}*/
3883 SCIP_CONSHDLRDATA* conshdlrdata;
3884
3885 assert( scip != NULL );
3886 assert( conshdlr != NULL );
3887 assert( nconss == 0 || conss != NULL );
3888
3889 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3890 assert(conshdlrdata != NULL);
3891
3892 if( conshdlrdata->linearize )
3893 {
3894 /* linearize all AND-constraints and remove the AND-constraints */
3895 SCIP_CONS* newcons;
3896 SCIP_CONS* cons;
3897 SCIP_CONSDATA* consdata;
3898 char consname[SCIP_MAXSTRLEN];
3899
3900 SCIP_VAR** vars;
3901 SCIP_Real* vals;
3902
3903 int nvars;
3904 int c, v;
3905
3906 /* allocate buffer array */
3907 SCIP_CALL( SCIPallocBufferArray(scip, &vars, 2) );
3908 SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
3909
3910 for( c = 0; c < nconss; ++c )
3911 {
3912 cons = conss[c];
3913 assert( cons != NULL );
3914
3915 /* only added constraints can be upgraded */
3916 if( !SCIPconsIsAdded(cons) )
3917 continue;
3918
3919 consdata = SCIPconsGetData(cons);
3920 assert( consdata != NULL );
3921 assert( consdata->resvar != NULL );
3922
3923 nvars = consdata->nvars;
3924
3925 if( !conshdlrdata->aggrlinearization )
3926 {
3927 vars[0] = consdata->resvar;
3928 vals[0] = 1.0;
3929 vals[1] = -1.0;
3930
3931 /* create operator linear constraints */
3932 for( v = 0; v < nvars; ++v )
3933 {
3934 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
3935 vars[1] = consdata->vars[v];
3936
3937 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, vars, vals, -SCIPinfinity(scip), 0.0,
3939 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3941 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3942
3943 /* add constraint */
3944 SCIP_CALL( SCIPaddCons(scip, newcons) );
3945 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3946 }
3947 }
3948
3949 /* reallocate buffer array */
3950 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, nvars + 1) );
3951 SCIP_CALL( SCIPreallocBufferArray(scip, &vals, nvars + 1) );
3952
3953 for( v = 0; v < nvars; ++v )
3954 {
3955 vars[v] = consdata->vars[v];
3956 vals[v] = -1.0;
3957 }
3958
3959 vars[nvars] = consdata->resvar;
3960
3961 if( conshdlrdata->aggrlinearization )
3962 {
3963 /* create additional linear constraint */
3964 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_operators", SCIPconsGetName(cons));
3965
3966 vals[nvars] = (SCIP_Real) nvars;
3967
3968 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -SCIPinfinity(scip), 0.0,
3970 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3972 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3973
3974 /* add constraint */
3975 SCIP_CALL( SCIPaddCons(scip, newcons) );
3976 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3977 }
3978
3979 /* create additional linear constraint */
3980 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
3981
3982 vals[nvars] = 1.0;
3983
3984 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -nvars + 1.0, SCIPinfinity(scip),
3986 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3988 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3989
3990 /* add constraint */
3991 SCIP_CALL( SCIPaddCons(scip, newcons) );
3992 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3993
3994 /* delete constraint */
3995 SCIP_CALL( SCIPdelCons(scip, cons) );
3996 }
3997
3998 /* free buffer array */
3999 SCIPfreeBufferArray(scip, &vars);
4000 SCIPfreeBufferArray(scip, &vals);
4001 }
4002
4003 return SCIP_OKAY;
4004}
4005
4006
4007#ifdef GMLGATEPRINTING
4008
4009/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
4010static
4011SCIP_DECL_CONSEXITPRE(consExitpreAnd)
4012{ /*lint --e{715}*/
4013 SCIP_HASHMAP* hashmap;
4014 FILE* gmlfile;
4015 char fname[SCIP_MAXSTRLEN];
4016 SCIP_CONS* cons;
4017 SCIP_CONSDATA* consdata;
4018 SCIP_VAR** activeconsvars;
4019 SCIP_VAR* activevar;
4020 int* varnodeids;
4021 SCIP_VAR** vars;
4022 int nvars;
4023 int nbinvars;
4024 int nintvars;
4025 int nimplvars;
4026 int ncontvars;
4027 int v;
4028 int c;
4029 int resid;
4030 int varid;
4031 int id = 1;
4032
4033 /* no AND-constraints available */
4034 if( nconss == 0 )
4035 return SCIP_OKAY;
4036
4037 nvars = SCIPgetNVars(scip);
4038
4039 /* no variables left anymore */
4040 if( nvars == 0 )
4041 return SCIP_OKAY;
4042
4043 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4044 SCIP_CALL( SCIPallocBufferArray(scip, &varnodeids, nvars) );
4045 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, &ncontvars) );
4046
4047 /* open gml file */
4048 (void) SCIPsnprintf(fname, SCIP_MAXSTRLEN, "and-gates%p.gml", scip);
4049 gmlfile = fopen(fname, "w");
4050
4051 if( gmlfile == NULL )
4052 {
4053 SCIPerrorMessage("cannot open graph file <%s>\n", fname);
4054 SCIPABORT();
4055 return SCIP_WRITEERROR; /*lint !e527*/
4056 }
4057
4058 /* create the variable mapping hash map */
4059 SCIP_CALL_FINALLY( SCIPhashmapCreate(&hashmap, SCIPblkmem(scip), nvars), fclose(gmlfile) );
4060
4061 /* write starting of gml file */
4062 SCIPgmlWriteOpening(gmlfile, TRUE);
4063
4064 /* walk over all AND-constraints */
4065 for( c = nconss - 1; c >= 0; --c )
4066 {
4067 cons = conss[c];
4068
4069 /* only handle active constraints */
4070 if( !SCIPconsIsActive(cons) )
4071 continue;
4072
4073 consdata = SCIPconsGetData(cons);
4074 assert(consdata != NULL);
4075
4076 /* only handle constraints which have operands */
4077 if( consdata->nvars == 0 )
4078 continue;
4079
4080 assert(consdata->vars != NULL);
4081 assert(consdata->resvar != NULL);
4082
4083 /* get active variable of resultant */
4084 activevar = SCIPvarGetProbvar(consdata->resvar);
4085
4086 /* check if we already found this variables */
4087 resid = SCIPhashmapGetImageInt(hashmap, activevar);
4088 assert(resid >= 0);
4089
4090 if( resid == 0 )
4091 {
4092 resid = id;
4093 ++id;
4094 SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activevar, resid) );
4095
4096 /* write new gml node for new resultant */
4097 SCIPgmlWriteNode(gmlfile, resid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4098 }
4099
4100 /* copy operands to get problem variables for */
4101 SCIP_CALL( SCIPduplicateBufferArray(scip, &activeconsvars, consdata->vars, consdata->nvars) );
4102
4103 /* get problem variables of operands */
4104 SCIPvarsGetProbvar(activeconsvars, consdata->nvars);
4105
4106 for( v = consdata->nvars - 1; v >= 0; --v )
4107 {
4108 /* check if we already found this variables */
4109 varid = SCIPhashmapGetImageInt(hashmap, activeconsvars[v]);
4110 if( varid == 0 )
4111 {
4112 varid = id;
4113 ++id;
4114 SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4115
4116 /* write new gml node for new operand */
4117 SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activeconsvars[v]), NULL, NULL, NULL);
4118 }
4119 /* write gml arc between resultant and operand */
4120 SCIPgmlWriteArc(gmlfile, resid, varid, NULL, NULL);
4121 }
4122
4123 /* free temporary memory for active constraint variables */
4124 SCIPfreeBufferArray(scip, &activeconsvars);
4125 }
4126
4127 /* write all remaining variables as nodes */
4128#ifdef SCIP_DISABLED_CODE
4129 for( v = nvars - 1; v >= 0; --v )
4130 {
4131 activevar = SCIPvarGetProbvar(vars[v]);
4132
4133 varid = SCIPhashmapGetImageInt(hashmap, activevar);
4134 assert(varid >= 0);
4135
4136 if( varid == 0 )
4137 {
4138 varid = id;
4139 ++id;
4140 SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4141
4142 /* write new gml node for new operand */
4143 SCIPgmlWriteNode(gmlfile, varid, SCIPvarGetName(activevar), NULL, NULL, NULL);
4144 }
4145 }
4146#endif
4147
4148 /* free the variable mapping hash map */
4149 SCIPhashmapFree(&hashmap);
4150
4151 SCIPgmlWriteClosing(gmlfile);
4152
4153 fclose(gmlfile);
4154
4155 SCIPfreeBufferArray(scip, &varnodeids);
4156 SCIPfreeBufferArray(scip, &vars);
4157
4158 return SCIP_OKAY;
4159}
4160#endif
4161
4162/** solving process initialization method of constraint handler */
4163static
4165{ /*lint --e{715}*/
4166 /* add nlrow representation to NLP, if NLP had been constructed */
4168 {
4169 int c;
4170 for( c = 0; c < nconss; ++c )
4171 {
4172 SCIP_CALL( addNlrow(scip, conss[c]) );
4173 }
4174 }
4175
4176 return SCIP_OKAY;
4177}
4178
4179/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4180static
4182{ /*lint --e{715}*/
4183 SCIP_CONSDATA* consdata;
4184 int c;
4185
4186 /* release and free the rows and nlrow of all constraints */
4187 for( c = 0; c < nconss; ++c )
4188 {
4189 consdata = SCIPconsGetData(conss[c]);
4190 assert(consdata != NULL);
4191
4192 SCIP_CALL( consdataFreeRows(scip, consdata) );
4193
4194 if( consdata->nlrow != NULL )
4195 {
4196 SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow) );
4197 }
4198 }
4199
4200 return SCIP_OKAY;
4201}
4202
4203
4204/** frees specific constraint data */
4205static
4207{ /*lint --e{715}*/
4208 SCIP_CONSHDLRDATA* conshdlrdata;
4209
4210 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4211 assert(conshdlrdata != NULL);
4212
4213 SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4214
4215 return SCIP_OKAY;
4216}
4217
4218
4219/** transforms constraint data into data belonging to the transformed problem */
4220static
4222{ /*lint --e{715}*/
4223 SCIP_CONSHDLRDATA* conshdlrdata;
4224 SCIP_CONSDATA* sourcedata;
4225 SCIP_CONSDATA* targetdata;
4226
4227 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4228 assert(conshdlrdata != NULL);
4229
4230 sourcedata = SCIPconsGetData(sourcecons);
4231 assert(sourcedata != NULL);
4232
4233 /* create target constraint data */
4234 SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
4235 sourcedata->nvars, sourcedata->vars, sourcedata->resvar, sourcedata->checkwhenupgr,
4236 sourcedata->notremovablewhenupgr) );
4237
4238 /* create target constraint */
4239 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4240 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4241 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4242 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4243 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4244
4245 return SCIP_OKAY;
4246}
4247
4248
4249/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4250static
4252{ /*lint --e{715}*/
4253 int i;
4254
4255 *infeasible = FALSE;
4256
4257 for( i = 0; i < nconss && !(*infeasible); i++ )
4258 {
4259 assert(SCIPconsIsInitial(conss[i]));
4260 SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4261 }
4262
4263 return SCIP_OKAY;
4264}
4265
4266
4267/** separation method of constraint handler for LP solutions */
4268static
4270{ /*lint --e{715}*/
4271 SCIP_Bool separated;
4272 SCIP_Bool cutoff;
4273 int c;
4274
4275 *result = SCIP_DIDNOTFIND;
4276
4277 /* separate all useful constraints */
4278 for( c = 0; c < nusefulconss; ++c )
4279 {
4280 SCIP_CALL( separateCons(scip, conss[c], NULL, &separated, &cutoff) );
4281 if ( cutoff )
4282 *result = SCIP_CUTOFF;
4283 else if ( separated )
4284 *result = SCIP_SEPARATED;
4285 }
4286
4287 /* combine constraints to get more cuts */
4288 /**@todo combine constraints to get further cuts */
4289
4290 return SCIP_OKAY;
4291}
4292
4293
4294/** separation method of constraint handler for arbitrary primal solutions */
4295static
4297{ /*lint --e{715}*/
4298 SCIP_Bool separated;
4299 SCIP_Bool cutoff;
4300 int c;
4301
4302 *result = SCIP_DIDNOTFIND;
4303
4304 /* separate all useful constraints */
4305 for( c = 0; c < nusefulconss; ++c )
4306 {
4307 SCIP_CALL( separateCons(scip, conss[c], sol, &separated, &cutoff) );
4308 if ( cutoff )
4309 *result = SCIP_CUTOFF;
4310 else if ( separated )
4311 *result = SCIP_SEPARATED;
4312 }
4313
4314 /* combine constraints to get more cuts */
4315 /**@todo combine constraints to get further cuts */
4316
4317 return SCIP_OKAY;
4318}
4319
4320
4321/** constraint enforcing method of constraint handler for LP solutions */
4322static
4324{ /*lint --e{715}*/
4325 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
4326
4327 return SCIP_OKAY;
4328}
4329
4330/** constraint enforcing method of constraint handler for relaxation solutions */
4331static
4333{ /*lint --e{715}*/
4334 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
4335
4336 return SCIP_OKAY;
4337}
4338
4339/** constraint enforcing method of constraint handler for pseudo solutions */
4340static
4342{ /*lint --e{715}*/
4343 SCIP_Bool violated;
4344 int i;
4345
4346 /* method is called only for integral solutions, because the enforcing priority is negative */
4347 for( i = 0; i < nconss; i++ )
4348 {
4349 SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
4350 if( violated )
4351 {
4352 *result = SCIP_INFEASIBLE;
4353 return SCIP_OKAY;
4354 }
4355 }
4356 *result = SCIP_FEASIBLE;
4357
4358 return SCIP_OKAY;
4359}
4360
4361/** feasibility check method of constraint handler and */
4362static
4364{ /*lint --e{715}*/
4365 SCIP_Bool violated;
4366 int i;
4367
4368 *result = SCIP_FEASIBLE;
4369
4370 for( i = 0; i < nconss && ( *result == SCIP_FEASIBLE || completely ); ++i )
4371 {
4372 SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
4373 if( violated )
4374 *result = SCIP_INFEASIBLE;
4375 }
4376
4377 return SCIP_OKAY;
4378}
4379
4380/** domain propagation method of constraint handler */
4381static
4383{ /*lint --e{715}*/
4384 SCIP_CONSHDLRDATA* conshdlrdata;
4385 SCIP_Bool cutoff;
4386 int nfixedvars;
4387 int nupgdconss;
4388 int c;
4389
4390 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4391 assert(conshdlrdata != NULL);
4392
4393 cutoff = FALSE;
4394 nfixedvars = 0;
4395 nupgdconss = 0;
4396
4397 /* propagate all useful constraints */
4398 for( c = 0; c < nusefulconss && !cutoff; ++c )
4399 {
4400 SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nupgdconss) );
4401 }
4402
4403 /* return the correct result */
4404 if( cutoff )
4405 *result = SCIP_CUTOFF;
4406 else if( nfixedvars > 0 || nupgdconss > 0 )
4407 *result = SCIP_REDUCEDDOM;
4408 else
4409 *result = SCIP_DIDNOTFIND;
4410
4411 return SCIP_OKAY;
4412}
4413
4414
4415/** presolving method of constraint handler */
4416static
4418{ /*lint --e{715}*/
4419 SCIP_CONSHDLRDATA* conshdlrdata;
4420 SCIP_CONS* cons;
4421 SCIP_CONSDATA* consdata;
4422 unsigned char* entries;
4423 SCIP_Bool cutoff;
4424 int oldnfixedvars;
4425 int oldnaggrvars;
4426 int oldnchgbds;
4427 int oldndelconss;
4428 int oldnupgdconss;
4429 int firstchange;
4430 int nentries;
4431 int c;
4432
4433 assert(result != NULL);
4434
4435 oldnfixedvars = *nfixedvars;
4436 oldnaggrvars = *naggrvars;
4437 oldnchgbds = *nchgbds;
4438 oldndelconss = *ndelconss;
4439 oldnupgdconss = *nupgdconss;
4440
4441 nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4442 SCIP_CALL( SCIPallocBufferArray(scip, &entries, nentries) );
4443
4444 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4445 assert(conshdlrdata != NULL);
4446
4447 /* process constraints */
4448 cutoff = FALSE;
4449 firstchange = INT_MAX;
4450 for( c = 0; c < nconss && !cutoff && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
4451 {
4452 cons = conss[c];
4453 assert(cons != NULL);
4454 consdata = SCIPconsGetData(cons);
4455 assert(consdata != NULL);
4456
4457 /* force presolving the constraint in the initial round */
4458 if( nrounds == 0 )
4459 consdata->propagated = FALSE;
4460
4461 /* remember the first changed constraint to begin the next aggregation round with */
4462 if( firstchange == INT_MAX && consdata->changed )
4463 firstchange = c;
4464
4465 /* propagate constraint */
4466 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4467
4468 /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4469 * fix resultant to zero if a pair of negated variables is contained in the operand variables
4470 */
4471 if( !cutoff && !SCIPconsIsDeleted(cons) )
4472 {
4473 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4474
4475 /* merge multiple occurances of variables or variables with their negated variables */
4476 SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4477 }
4478
4479 if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
4480 {
4481 assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
4482
4483 /* if only one variable is left, the resultant has to be equal to this single variable */
4484 if( consdata->nvars == 1 )
4485 {
4486 SCIP_Bool redundant;
4487 SCIP_Bool aggregated;
4488
4489 SCIPdebugMsg(scip, "AND-constraint <%s> has only one variable not fixed to 1.0\n", SCIPconsGetName(cons));
4490
4491 assert(consdata->vars != NULL);
4492 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
4493 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
4494
4495 /* aggregate variables: resultant - operand == 0 */
4496 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
4497 &cutoff, &redundant, &aggregated) );
4498 assert(redundant || SCIPdoNotAggr(scip));
4499
4500 if( aggregated )
4501 {
4502 assert(redundant);
4503 (*naggrvars)++;
4504 }
4505
4506 if( redundant )
4507 {
4508 /* delete constraint */
4509 SCIP_CALL( SCIPdelCons(scip, cons) );
4510 (*ndelconss)++;
4511 }
4512 }
4513 else if( !consdata->impladded )
4514 {
4515 int i;
4516
4517 /* add implications: resultant == 1 -> all operands == 1 */
4518 for( i = 0; i < consdata->nvars && !cutoff; ++i )
4519 {
4520 int nimplbdchgs;
4521
4522 SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, TRUE, consdata->vars[i],
4523 SCIP_BOUNDTYPE_LOWER, 1.0, &cutoff, &nimplbdchgs) );
4524 (*nchgbds) += nimplbdchgs;
4525 }
4526 consdata->impladded = TRUE;
4527 }
4528
4529 /* if in r = x and y, the resultant is fixed to zero, add implication x = 1 -> y = 0 */
4530 if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
4531 && SCIPvarGetUbGlobal(consdata->resvar) < 0.5 )
4532 {
4533 int nimplbdchgs;
4534
4535 SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], TRUE, consdata->vars[1],
4536 SCIP_BOUNDTYPE_UPPER, 0.0, &cutoff, &nimplbdchgs) );
4537 (*nchgbds) += nimplbdchgs;
4538 consdata->opimpladded = TRUE;
4539 }
4540 }
4541 }
4542
4543 /* perform dual presolving on AND-constraints */
4544 if( conshdlrdata->dualpresolving && !cutoff && !SCIPisStopped(scip) && SCIPallowStrongDualReds(scip))
4545 {
4546 SCIP_CALL( dualPresolve(scip, conss, nconss, conshdlrdata->eventhdlr, &entries, &nentries, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, nupgdconss, naddconss) );
4547 }
4548
4549 /* check for cliques inside the AND constraint */
4550 if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4551 {
4552 for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4553 {
4554 cons = conss[c];
4555 assert(cons != NULL);
4556
4557 if( !SCIPconsIsActive(cons) )
4558 continue;
4559
4560 /* cliquePresolve() may aggregate variables which need to be removed from other constraints, we also need
4561 * to make sure that we remove fixed variables by calling propagateCons() to make sure that applyFixing()
4562 * and mergeMultiples() work
4563 */
4564 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4565
4566 if( !cutoff && !SCIPconsIsDeleted(cons) )
4567 {
4568 /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4569 * fix resultant to zero if a pair of negated variables is contained in the operand variables
4570 */
4571 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4572 SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4573
4574 /* check if at least two operands are in one clique */
4575 SCIP_CALL( cliquePresolve(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, naddconss) );
4576 }
4577 }
4578 }
4579
4580 /* process pairs of constraints: check them for equal operands in order to aggregate resultants;
4581 * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
4582 * (otherwise, we delay the presolving to be called again next time)
4583 */
4584 if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4585 {
4586 if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4587 {
4588 if( firstchange < nconss )
4589 {
4590 /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4591 SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, &cutoff, naggrvars, ndelconss) );
4592 oldnaggrvars = *naggrvars;
4593 }
4594 }
4595 }
4596
4597 if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4598 {
4599 if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4600 {
4601 SCIP_Longint npaircomparisons;
4602 npaircomparisons = 0;
4603 oldndelconss = *ndelconss;
4604
4605 for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4606 {
4607 if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
4608 {
4609 npaircomparisons += ((SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange));
4610
4611 SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c, &cutoff, naggrvars, nchgbds,
4612 ndelconss) );
4613
4614 if( npaircomparisons > NMINCOMPARISONS )
4615 {
4616 if( ((*ndelconss - oldndelconss) + (*naggrvars - oldnaggrvars) + (*nchgbds - oldnchgbds)/2.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
4617 break;
4618 oldndelconss = *ndelconss;
4619 oldnaggrvars = *naggrvars;
4620 oldnchgbds = *nchgbds;
4621
4622 npaircomparisons = 0;
4623 }
4624 }
4625 }
4626 }
4627 }
4628
4629 SCIPfreeBufferArray(scip, &entries);
4630
4631 /* return the correct result code */
4632 if( cutoff )
4633 *result = SCIP_CUTOFF;
4634 else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
4635 || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4636 *result = SCIP_SUCCESS;
4637 else
4638 *result = SCIP_DIDNOTFIND;
4639
4640 return SCIP_OKAY;
4641}
4642
4643
4644/** propagation conflict resolving method of constraint handler */
4645static
4647{ /*lint --e{715}*/
4648 SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
4649
4650 return SCIP_OKAY;
4651}
4652
4653
4654/** variable rounding lock method of constraint handler */
4655static
4657{ /*lint --e{715}*/
4658 SCIP_CONSDATA* consdata;
4659 int i;
4660
4661 assert(locktype == SCIP_LOCKTYPE_MODEL);
4662
4663 consdata = SCIPconsGetData(cons);
4664 assert(consdata != NULL);
4665
4666 /* resultant variable */
4667 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->resvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4668
4669 /* operand variables */
4670 for( i = 0; i < consdata->nvars; ++i )
4671 {
4672 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4673 }
4674
4675 return SCIP_OKAY;
4676}
4677
4678/** constraint activation notification method of constraint handler */
4679static
4681{ /*lint --e{715}*/
4683 {
4684 SCIP_CALL( addNlrow(scip, cons) );
4685 }
4686
4687 return SCIP_OKAY;
4688}
4689
4690/** constraint deactivation notification method of constraint handler */
4691static
4693{ /*lint --e{715}*/
4694 SCIP_CONSDATA* consdata;
4695
4696 assert(cons != NULL);
4697
4698 consdata = SCIPconsGetData(cons);
4699 assert(consdata != NULL);
4700
4701 /* remove row from NLP, if still in solving
4702 * if we are in exitsolve, the whole NLP will be freed anyway
4703 */
4704 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow != NULL )
4705 {
4706 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow) );
4707 }
4708
4709 return SCIP_OKAY;
4710}
4711
4712/** constraint display method of constraint handler */
4713static
4715{ /*lint --e{715}*/
4716 assert( scip != NULL );
4717 assert( conshdlr != NULL );
4718 assert( cons != NULL );
4719
4721
4722 return SCIP_OKAY;
4723}
4724
4725/** constraint copying method of constraint handler */
4726static
4728{ /*lint --e{715}*/
4729 SCIP_VAR** sourcevars;
4730 SCIP_VAR** vars;
4731 SCIP_VAR* sourceresvar;
4732 SCIP_VAR* resvar;
4733 const char* consname;
4734 int nvars;
4735 int v;
4736
4737 assert(valid != NULL);
4738 (*valid) = TRUE;
4739
4740 sourceresvar = SCIPgetResultantAnd(sourcescip, sourcecons);
4741
4742 /* map resultant to active variable of the target SCIP */
4743 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
4744 assert(!(*valid) || resvar != NULL);
4745
4746 /* we do not copy, if a variable is missing */
4747 if( !(*valid) )
4748 return SCIP_OKAY;
4749
4750 /* map operand variables to active variables of the target SCIP */
4751 sourcevars = SCIPgetVarsAnd(sourcescip, sourcecons);
4752 nvars = SCIPgetNVarsAnd(sourcescip, sourcecons);
4753
4754 if( nvars == -1 )
4755 return SCIP_INVALIDCALL;
4756
4757 /* allocate buffer array */
4758 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4759
4760 for( v = 0; v < nvars; ++v )
4761 {
4762 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
4763 assert(!(*valid) || vars[v] != NULL);
4764
4765 /* we do not copy, if a variable is missing */
4766 if( !(*valid) )
4767 goto TERMINATE;
4768 }
4769
4770 if( name != NULL )
4771 consname = name;
4772 else
4773 consname = SCIPconsGetName(sourcecons);
4774
4775 /* creates and captures a AND-constraint */
4776 SCIP_CALL( SCIPcreateConsAnd(scip, cons, consname, resvar, nvars, vars,
4777 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4778
4779 TERMINATE:
4780 /* free buffer array */
4781 SCIPfreeBufferArray(scip, &vars);
4782
4783 return SCIP_OKAY;
4784}
4785
4786/** constraint parsing method of constraint handler */
4787static
4789{ /*lint --e{715}*/
4790 SCIP_VAR** vars;
4791 SCIP_VAR* resvar;
4792 char* endptr;
4793 int requiredsize;
4794 int varssize;
4795 int nvars;
4796
4797 SCIPdebugMsg(scip, "parse <%s> as AND-constraint\n", str);
4798
4799 *success = FALSE;
4800
4801 /* parse variable name of resultant */
4802 SCIP_CALL( SCIPparseVarName(scip, str, &resvar, &endptr) );
4803
4804 if( resvar == NULL )
4805 {
4806 SCIPerrorMessage("resultant variable does not exist\n");
4807 }
4808 else
4809 {
4810 char* strcopy = NULL;
4811 char* startptr;
4812
4813 str = endptr;
4814
4815 /* cutoff "== and(" form the constraint string */
4816 startptr = strchr((char*)str, '(');
4817
4818 if( startptr == NULL )
4819 {
4820 SCIPerrorMessage("missing starting character '(' parsing AND-constraint\n");
4821 return SCIP_OKAY;
4822 }
4823
4824 /* skip '(' */
4825 ++startptr;
4826
4827 /* find end character ')' */
4828 endptr = strrchr(startptr, ')');
4829
4830 if( endptr == NULL )
4831 {
4832 SCIPerrorMessage("missing ending character ')' parsing AND-constraint\n");
4833 return SCIP_OKAY;
4834 }
4835 assert(endptr >= startptr);
4836
4837 if( endptr > startptr )
4838 {
4839 /* copy string for parsing; note that SCIPskipSpace() in SCIPparseVarsList() requires that strcopy ends with '\0' */
4840 SCIP_CALL( SCIPduplicateBufferArray(scip, &strcopy, startptr, (int)(endptr-startptr+1)) );
4841 strcopy[endptr-startptr] = '\0';
4842 varssize = 100;
4843 nvars = 0;
4844
4845 /* allocate buffer array for variables */
4846 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4847
4848 /* parse string */
4849 SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4850
4851 if( *success )
4852 {
4853 /* check if the size of the variable array was great enough */
4854 if( varssize < requiredsize )
4855 {
4856 /* reallocate memory */
4857 varssize = requiredsize;
4858 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4859
4860 /* parse string again with the correct size of the variable array */
4861 SCIP_CALL( SCIPparseVarsList(scip, strcopy, vars, &nvars, varssize, &requiredsize, &endptr, ',', success) );
4862 }
4863
4864 assert(*success);
4865 assert(varssize >= requiredsize);
4866
4867 /* create AND-constraint */
4868 SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
4869 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4870 }
4871
4872 /* free variable buffer */
4873 SCIPfreeBufferArray(scip, &vars);
4874 SCIPfreeBufferArray(scip, &strcopy);
4875 }
4876 else
4877 {
4878 if( !modifiable )
4879 {
4880 SCIPerrorMessage("cannot create empty AND-constraint\n");
4881 return SCIP_OKAY;
4882 }
4883
4884 /* create empty AND-constraint */
4885 SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, 0, NULL,
4886 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4887
4888 *success = TRUE;
4889 }
4890 }
4891
4892 return SCIP_OKAY;
4893}
4894
4895/** constraint method of constraint handler which returns the variables (if possible) */
4896static
4898{ /*lint --e{715}*/
4899 SCIP_CONSDATA* consdata;
4900
4901 consdata = SCIPconsGetData(cons);
4902 assert(consdata != NULL);
4903
4904 if( varssize < consdata->nvars + 1 )
4905 (*success) = FALSE;
4906 else
4907 {
4908 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4909 vars[consdata->nvars] = consdata->resvar;
4910 (*success) = TRUE;
4911 }
4912
4913 return SCIP_OKAY;
4914}
4915
4916/** constraint method of constraint handler which returns the number of variable (if possible) */
4917static
4919{ /*lint --e{715}*/
4920 SCIP_CONSDATA* consdata;
4921
4922 assert(cons != NULL);
4923
4924 consdata = SCIPconsGetData(cons);
4925 assert(consdata != NULL);
4926
4927 (*nvars) = consdata->nvars + 1;
4928 (*success) = TRUE;
4929
4930 return SCIP_OKAY;
4931}
4932
4933/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
4934static
4935SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphAnd)
4936{ /*lint --e{715}*/
4937 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_PERM, cons, graph, success) );
4938
4939 return SCIP_OKAY;
4940}
4941
4942/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
4943static
4944SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphAnd)
4945{ /*lint --e{715}*/
4946 SCIP_CALL( addSymmetryInformation(scip, SYM_SYMTYPE_SIGNPERM, cons, graph, success) );
4947
4948 return SCIP_OKAY;
4949}
4950
4951/*
4952 * Callback methods of event handler
4953 */
4954
4955static
4957{ /*lint --e{715}*/
4958 SCIP_CONSDATA* consdata;
4959
4960 assert(eventhdlr != NULL);
4961 assert(eventdata != NULL);
4962 assert(event != NULL);
4963
4964 consdata = (SCIP_CONSDATA*)eventdata;
4965 assert(consdata != NULL);
4966
4967 /* check, if the variable was fixed to zero */
4969 consdata->nofixedzero = FALSE;
4970
4971 consdata->propagated = FALSE;
4972
4973 return SCIP_OKAY;
4974}
4975
4976
4977/*
4978 * constraint specific interface methods
4979 */
4980
4981/** creates the handler for AND-constraints and includes it in SCIP */
4983 SCIP* scip /**< SCIP data structure */
4984 )
4985{
4986 SCIP_CONSHDLRDATA* conshdlrdata;
4987 SCIP_CONSHDLR* conshdlr;
4988 SCIP_EVENTHDLR* eventhdlr;
4989
4990 /* create event handler for events on variables */
4992 eventExecAnd, NULL) );
4993
4994 /* create constraint handler data */
4995 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
4996
4997 /* include constraint handler */
5000 consEnfolpAnd, consEnfopsAnd, consCheckAnd, consLockAnd,
5001 conshdlrdata) );
5002
5003 assert(conshdlr != NULL);
5004
5005 /* set non-fundamental callbacks via specific setter functions */
5006 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyAnd, consCopyAnd) );
5007 SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveAnd) );
5008 SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveAnd) );
5009 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteAnd) );
5010#ifdef GMLGATEPRINTING
5011 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreAnd) );
5012#endif
5013 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolAnd) );
5014 SCIP_CALL( SCIPsetConshdlrExitsol(scip, conshdlr, consExitsolAnd) );
5015 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeAnd) );
5016 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsAnd) );
5017 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsAnd) );
5018 SCIP_CALL( SCIPsetConshdlrInitpre(scip, conshdlr, consInitpreAnd) );
5019 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpAnd) );
5020 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseAnd) );
5022 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintAnd) );
5025 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropAnd) );
5026 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpAnd, consSepasolAnd, CONSHDLR_SEPAFREQ,
5028 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransAnd) );
5029 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxAnd) );
5030 SCIP_CALL( SCIPsetConshdlrGetPermsymGraph(scip, conshdlr, consGetPermsymGraphAnd) );
5031 SCIP_CALL( SCIPsetConshdlrGetSignedPermsymGraph(scip, conshdlr, consGetSignedPermsymGraphAnd) );
5032
5033 /* add AND-constraint handler parameters */
5035 "constraints/" CONSHDLR_NAME "/presolpairwise",
5036 "should pairwise constraint comparison be performed in presolving?",
5037 &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5039 "constraints/and/presolusehashing",
5040 "should hash table be used for detecting redundant constraints in advance",
5041 &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
5043 "constraints/" CONSHDLR_NAME "/linearize",
5044 "should the AND-constraint get linearized and removed (in presolving)?",
5045 &conshdlrdata->linearize, TRUE, DEFAULT_LINEARIZE, NULL, NULL) );
5047 "constraints/" CONSHDLR_NAME "/enforcecuts",
5048 "should cuts be separated during LP enforcing?",
5049 &conshdlrdata->enforcecuts, TRUE, DEFAULT_ENFORCECUTS, NULL, NULL) );
5051 "constraints/" CONSHDLR_NAME "/aggrlinearization",
5052 "should an aggregated linearization be used?",
5053 &conshdlrdata->aggrlinearization, TRUE, DEFAULT_AGGRLINEARIZATION, NULL, NULL) );
5055 "constraints/" CONSHDLR_NAME "/upgraderesultant",
5056 "should all binary resultant variables be upgraded to implicit binary variables?",
5057 &conshdlrdata->upgrresultant, TRUE, DEFAULT_UPGRRESULTANT, NULL, NULL) );
5059 "constraints/" CONSHDLR_NAME "/dualpresolving",
5060 "should dual presolving be performed?",
5061 &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
5062
5063 return SCIP_OKAY;
5064}
5065
5066/** creates and captures a AND-constraint
5067 *
5068 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5069 */
5071 SCIP* scip, /**< SCIP data structure */
5072 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5073 const char* name, /**< name of constraint */
5074 SCIP_VAR* resvar, /**< resultant variable of the operation */
5075 int nvars, /**< number of operator variables in the constraint */
5076 SCIP_VAR** vars, /**< array with operator variables of constraint */
5077 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5078 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5079 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5080 * Usually set to TRUE. */
5081 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5082 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5083 SCIP_Bool check, /**< should the constraint be checked for feasibility?
5084 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5085 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5086 * Usually set to TRUE. */
5087 SCIP_Bool local, /**< is constraint only valid locally?
5088 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5089 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5090 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5091 * adds coefficients to this constraint. */
5092 SCIP_Bool dynamic, /**< is constraint subject to aging?
5093 * Usually set to FALSE. Set to TRUE for own cuts which
5094 * are separated as constraints. */
5095 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5096 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5097 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5098 * if it may be moved to a more global node?
5099 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5100 )
5101{
5102 SCIP_CONSHDLR* conshdlr;
5103 SCIP_CONSHDLRDATA* conshdlrdata;
5104 SCIP_CONSDATA* consdata;
5105 SCIP_Bool infeasible;
5106
5107 /* find the AND-constraint handler */
5108 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5109 if( conshdlr == NULL )
5110 {
5111 SCIPerrorMessage("AND-constraint handler not found\n");
5112 return SCIP_PLUGINNOTFOUND;
5113 }
5114
5115 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5116 assert(conshdlrdata != NULL);
5117
5118 /* upgrade binary resultant variable to an implicit binary variable */
5119 /* @todo add implicit upgrade in presolving, improve decision making for upgrade by creating an implication graph */
5120 if( conshdlrdata->upgrresultant && SCIPvarGetType(resvar) == SCIP_VARTYPE_BINARY
5121#if 1 /* todo delete following hack,
5122 * the following avoids upgrading not artificial variables, for example and-resultants which are generated
5123 * from the gate presolver, it seems better to not upgrade these variables
5124 */
5125 && strlen(SCIPvarGetName(resvar)) > strlen(ARTIFICIALVARNAMEPREFIX) && strncmp(SCIPvarGetName(resvar), ARTIFICIALVARNAMEPREFIX, strlen(ARTIFICIALVARNAMEPREFIX)) == 0 )
5126#else
5127 )
5128#endif
5129 {
5130 SCIP_VAR* activeresvar;
5131 SCIP_VAR* activevar;
5132 int v;
5133
5134 if( SCIPisTransformed(scip) )
5135 activeresvar = SCIPvarGetProbvar(resvar);
5136 else
5137 activeresvar = resvar;
5138
5139 if( SCIPvarGetType(activeresvar) == SCIP_VARTYPE_BINARY )
5140 {
5141 /* check if we can upgrade the variable type of the resultant */
5142 for( v = nvars - 1; v >= 0; --v )
5143 {
5144 if( SCIPisTransformed(scip) )
5145 activevar = SCIPvarGetProbvar(vars[v]);
5146 else
5147 activevar = vars[v];
5148
5149 if( activevar == activeresvar || SCIPvarGetType(activevar) == SCIP_VARTYPE_IMPLINT )
5150 break;
5151 }
5152
5153 /* upgrade the type of the resultant */
5154 if( v < 0 )
5155 {
5156 SCIP_CALL( SCIPchgVarType(scip, resvar, SCIP_VARTYPE_IMPLINT, &infeasible) );
5157 assert(!infeasible);
5158 }
5159 }
5160 }
5161
5162 /* create constraint data */
5163 SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar, FALSE, FALSE) );
5164
5165 /* create constraint */
5166 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5167 local, modifiable, dynamic, removable, stickingatnode) );
5168
5169 return SCIP_OKAY;
5170}
5171
5172/** creates and captures an AND-constraint
5173 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5174 * method SCIPcreateConsAnd(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5175 *
5176 * @see SCIPcreateConsAnd() for information about the basic constraint flag configuration
5177 *
5178 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5179 */
5181 SCIP* scip, /**< SCIP data structure */
5182 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5183 const char* name, /**< name of constraint */
5184 SCIP_VAR* resvar, /**< resultant variable of the operation */
5185 int nvars, /**< number of operator variables in the constraint */
5186 SCIP_VAR** vars /**< array with operator variables of constraint */
5187 )
5188{
5189 assert(scip != NULL);
5190
5191 SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
5193
5194 return SCIP_OKAY;
5195}
5196
5197
5198/** gets number of variables in AND-constraint */
5200 SCIP* scip, /**< SCIP data structure */
5201 SCIP_CONS* cons /**< constraint data */
5202 )
5203{
5204 SCIP_CONSDATA* consdata;
5205
5206 assert(scip != NULL);
5207 assert(cons != NULL);
5208
5209 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5210 {
5211 SCIPerrorMessage("constraint is not an AND-constraint\n");
5212 SCIPABORT();
5213 return -1; /*lint !e527*/
5214 }
5215
5216 consdata = SCIPconsGetData(cons);
5217 assert(consdata != NULL);
5218
5219 return consdata->nvars;
5220}
5221
5222/** gets array of variables in AND-constraint */
5224 SCIP* scip, /**< SCIP data structure */
5225 SCIP_CONS* cons /**< constraint data */
5226 )
5227{ /*lint --e{715}*/
5228 SCIP_CONSDATA* consdata;
5229
5230 assert(scip != NULL);
5231 assert(cons != NULL);
5232
5233 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5234 {
5235 SCIPerrorMessage("constraint is not an AND-constraint\n");
5236 SCIPABORT();
5237 return NULL; /*lint !e527*/
5238 }
5239
5240 consdata = SCIPconsGetData(cons);
5241 assert(consdata != NULL);
5242
5243 return consdata->vars;
5244}
5245
5246
5247/** gets the resultant variable in AND-constraint */ /*lint -e715*/
5249 SCIP* scip, /**< SCIP data structure */
5250 SCIP_CONS* cons /**< constraint data */
5251 )
5252{
5253 SCIP_CONSDATA* consdata;
5254
5255 assert(cons != NULL);
5256
5257 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5258 {
5259 SCIPerrorMessage("constraint is not an AND-constraint\n");
5260 SCIPABORT();
5261 return NULL; /*lint !e527*/
5262 }
5263
5264 consdata = SCIPconsGetData(cons);
5265 assert(consdata != NULL);
5266
5267 return consdata->resvar;
5268}
5269
5270/** return if the variables of the AND-constraint are sorted with respect to their indices */
5272 SCIP* scip, /**< SCIP data structure */
5273 SCIP_CONS* cons /**< constraint data */
5274 )
5275{
5276 SCIP_CONSDATA* consdata;
5277
5278 assert(scip != NULL);
5279 assert(cons != NULL);
5280
5281 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5282 {
5283 SCIPerrorMessage("constraint is not an AND-constraint\n");
5284 SCIPABORT();
5285 return FALSE; /*lint !e527*/
5286 }
5287
5288 consdata = SCIPconsGetData(cons);
5289 assert(consdata != NULL);
5290
5291 return consdata->sorted;
5292}
5293
5294/** sort the variables of the AND-constraint with respect to their indices */
5296 SCIP* scip, /**< SCIP data structure */
5297 SCIP_CONS* cons /**< constraint data */
5298 )
5299{
5300 SCIP_CONSDATA* consdata;
5301
5302 assert(scip != NULL);
5303 assert(cons != NULL);
5304
5305 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5306 {
5307 SCIPerrorMessage("constraint is not an AND-constraint\n");
5308 SCIPABORT();
5309 return SCIP_INVALIDDATA; /*lint !e527*/
5310 }
5311
5312 consdata = SCIPconsGetData(cons);
5313 assert(consdata != NULL);
5314
5315 consdataSort(consdata);
5316 assert(consdata->sorted);
5317
5318 return SCIP_OKAY;
5319}
5320
5321/** when 'upgrading' the given AND-constraint, should the check flag for the upgraded constraint be set to TRUE, even if
5322 * the check flag of this AND-constraint is set to FALSE?
5323 */
5325 SCIP* scip, /**< SCIP data structure */
5326 SCIP_CONS* cons, /**< constraint data */
5327 SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be checked,
5328 * even if the check flag of the AND-constraint is set to FALSE
5329 */
5330 )
5331{
5332 SCIP_CONSDATA* consdata;
5333
5334 assert(scip != NULL);
5335 assert(cons != NULL);
5336
5337 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5338 {
5339 SCIPerrorMessage("constraint is not an AND-constraint\n");
5340 SCIPABORT();
5341 return SCIP_INVALIDDATA; /*lint !e527*/
5342 }
5343
5344 consdata = SCIPconsGetData(cons);
5345 assert(consdata != NULL);
5346
5347 consdata->checkwhenupgr = flag;
5348
5349 return SCIP_OKAY;
5350}
5351
5352/** when 'upgrading' the given AND-constraint, should the removable flag for the upgraded constraint be set to FALSE,
5353 * even if the removable flag of this AND-constraint is set to TRUE?
5354 */
5356 SCIP* scip, /**< SCIP data structure */
5357 SCIP_CONS* cons, /**< constraint data */
5358 SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be not
5359 * removable, even if the removable flag of the AND-constraint is set to
5360 * TRUE
5361 */
5362 )
5363{
5364 SCIP_CONSDATA* consdata;
5365
5366 assert(scip != NULL);
5367 assert(cons != NULL);
5368
5369 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
5370 {
5371 SCIPerrorMessage("constraint is not an AND-constraint\n");
5372 SCIPABORT();
5373 return SCIP_INVALIDDATA; /*lint !e527*/
5374 }
5375
5376 consdata = SCIPconsGetData(cons);
5377 assert(consdata != NULL);
5378
5379 consdata->notremovablewhenupgr = flag;
5380
5381 return SCIP_OKAY;
5382}
SCIP_Real * r
Definition: circlepacking.c:59
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
Definition: cons_and.c:972
enum Proprule PROPRULE
Definition: cons_and.c:179
static SCIP_DECL_CONSACTIVE(consActiveAnd)
Definition: cons_and.c:4680
static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA *consdata)
Definition: cons_and.c:515
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file)
Definition: cons_and.c:596
static SCIP_RETCODE consdataCatchWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int *filterpos)
Definition: cons_and.c:249
static SCIP_RETCODE consdataDropEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:322
#define DEFAULT_DUALPRESOLVING
Definition: cons_and.c:110
static SCIP_RETCODE dualPresolve(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars, int *nchgcoefs, int *ndelconss, int *nupgdconss, int *naddconss)
Definition: cons_and.c:2027
static SCIP_RETCODE consdataSwitchWatchedvars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition: cons_and.c:348
#define CONSHDLR_NEEDSCONS
Definition: cons_and.c:97
#define CONSHDLR_SEPAFREQ
Definition: cons_and.c:90
static SCIP_DECL_CONSDELETE(consDeleteAnd)
Definition: cons_and.c:4206
static SCIP_DECL_HASHKEYEQ(hashKeyEqAndcons)
Definition: cons_and.c:3335
static SCIP_DECL_EVENTEXEC(eventExecAnd)
Definition: cons_and.c:4956
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition: cons_and.c:681
#define CONSHDLR_CHECKPRIORITY
Definition: cons_and.c:89
static SCIP_DECL_CONSFREE(consFreeAnd)
Definition: cons_and.c:3863
#define CONSHDLR_DESC
Definition: cons_and.c:86
static SCIP_RETCODE consdataFixOperandsOne(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1353
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition: cons_and.c:1197
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
Definition: cons_and.c:621
static SCIP_DECL_CONSCOPY(consCopyAnd)
Definition: cons_and.c:4727
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:925
#define CONSHDLR_PROP_TIMING
Definition: cons_and.c:100
#define HASHSIZE_ANDCONS
Definition: cons_and.c:112
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition: cons_and.c:236
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_and.c:202
static SCIP_DECL_CONSENFOPS(consEnfopsAnd)
Definition: cons_and.c:4341
static SCIP_RETCODE analyzeZeroResultant(SCIP *scip, SCIP_CONS *cons, int watchedvar1, int watchedvar2, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1518
static SCIP_DECL_CONSINITPRE(consInitpreAnd)
Definition: cons_and.c:3881
static SCIP_DECL_HASHGETKEY(hashGetKeyAndcons)
Definition: cons_and.c:3327
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr, int nvars, SCIP_VAR **vars, SCIP_VAR *resvar, SCIP_Bool checkwhenupgr, SCIP_Bool notremovablewhenupgr)
Definition: cons_and.c:432
#define DEFAULT_UPGRRESULTANT
Definition: cons_and.c:109
#define CONSHDLR_MAXPREROUNDS
Definition: cons_and.c:94
static SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(consGetSignedPermsymGraphAnd)
Definition: cons_and.c:4944
static SCIP_RETCODE consdataFixResultantZero(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *resvar, int pos, SCIP_Bool *cutoff, int *nfixedvars)
Definition: cons_and.c:1314
static SCIP_DECL_CONSENFORELAX(consEnforelaxAnd)
Definition: cons_and.c:4332
#define DEFAULT_PRESOLPAIRWISE
Definition: cons_and.c:105
#define CONSHDLR_SEPAPRIORITY
Definition: cons_and.c:87
static SCIP_RETCODE analyzeConflictOne(SCIP *scip, SCIP_CONS *cons, int falsepos)
Definition: cons_and.c:1246
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, int *firstchange, SCIP_Bool *cutoff, int *naggrvars, int *ndelconss)
Definition: cons_and.c:3405
static SCIP_DECL_CONSRESPROP(consRespropAnd)
Definition: cons_and.c:4646
static SCIP_DECL_CONSSEPASOL(consSepasolAnd)
Definition: cons_and.c:4296
#define DEFAULT_LINEARIZE
Definition: cons_and.c:106
static SCIP_RETCODE cliquePresolve(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars, int *nchgcoefs, int *ndelconss, int *naddconss)
Definition: cons_and.c:2679
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, SCIP_Bool *cutoff, int *naggrvars, int *nbdchgs, int *ndelconss)
Definition: cons_and.c:3582
static SCIP_DECL_CONSTRANS(consTransAnd)
Definition: cons_and.c:4221
static SCIP_RETCODE consdataLinearize(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1407
static SCIP_DECL_CONSLOCK(consLockAnd)
Definition: cons_and.c:4656
static SCIP_DECL_CONSINITLP(consInitlpAnd)
Definition: cons_and.c:4251
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
Definition: cons_and.c:3786
static SCIP_DECL_CONSSEPALP(consSepalpAnd)
Definition: cons_and.c:4269
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition: cons_and.c:188
static SCIP_DECL_CONSEXITSOL(consExitsolAnd)
Definition: cons_and.c:4181
static SCIP_DECL_CONSGETPERMSYMGRAPH(consGetPermsymGraphAnd)
Definition: cons_and.c:4935
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num)
Definition: cons_and.c:408
Proprule
Definition: cons_and.c:172
@ PROPRULE_2
Definition: cons_and.c:175
@ PROPRULE_1
Definition: cons_and.c:174
@ PROPRULE_3
Definition: cons_and.c:176
@ PROPRULE_INVALID
Definition: cons_and.c:173
@ PROPRULE_4
Definition: cons_and.c:177
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool printreason, SCIP_Bool *violated)
Definition: cons_and.c:1085
#define DEFAULT_PRESOLUSEHASHING
Definition: cons_and.c:113
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:546
static SCIP_DECL_CONSPARSE(consParseAnd)
Definition: cons_and.c:4788
static SCIP_RETCODE consdataDropWatchedEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int pos, int filterpos)
Definition: cons_and.c:273
#define MINGAINPERNMINCOMPARISONS
Definition: cons_and.c:115
static SCIP_RETCODE analyzeConflictZero(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:1278
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyAnd)
Definition: cons_and.c:3847
static SCIP_DECL_CONSINITSOL(consInitsolAnd)
Definition: cons_and.c:4164
#define CONSHDLR_PROPFREQ
Definition: cons_and.c:91
static SCIP_DECL_CONSDEACTIVE(consDeactiveAnd)
Definition: cons_and.c:4692
#define NMINCOMPARISONS
Definition: cons_and.c:114
#define DEFAULT_ENFORCECUTS
Definition: cons_and.c:107
#define CONSHDLR_PRESOLTIMING
Definition: cons_and.c:99
static SCIP_DECL_CONSGETNVARS(consGetNVarsAnd)
Definition: cons_and.c:4918
static void consdataSort(SCIP_CONSDATA *consdata)
Definition: cons_and.c:744
static SCIP_DECL_CONSPROP(consPropAnd)
Definition: cons_and.c:4382
static SCIP_RETCODE addNlrow(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:1032
static SCIP_DECL_CONSPRINT(consPrintAnd)
Definition: cons_and.c:4714
#define CONSHDLR_EAGERFREQ
Definition: cons_and.c:92
#define EVENTHDLR_DESC
Definition: cons_and.c:103
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:216
static SCIP_DECL_HASHKEYVAL(hashKeyValAndcons)
Definition: cons_and.c:3381
static SCIP_DECL_CONSENFOLP(consEnfolpAnd)
Definition: cons_and.c:4323
static SCIP_DECL_CONSPRESOL(consPresolAnd)
Definition: cons_and.c:4417
#define CONSHDLR_ENFOPRIORITY
Definition: cons_and.c:88
static SCIP_DECL_CONSCHECK(consCheckAnd)
Definition: cons_and.c:4363
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int *nchgcoefs)
Definition: cons_and.c:825
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
Definition: cons_and.c:1941
#define CONSHDLR_DELAYSEPA
Definition: cons_and.c:95
static SCIP_RETCODE mergeMultiples(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, unsigned char **entries, int *nentries, int *nfixedvars, int *nchgcoefs, int *ndelconss)
Definition: cons_and.c:1579
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition: cons_and.c:3525
#define CONSHDLR_NAME
Definition: cons_and.c:85
#define EVENTHDLR_NAME
Definition: cons_and.c:102
#define DEFAULT_AGGRLINEARIZATION
Definition: cons_and.c:108
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition: cons_and.c:1736
#define CONSHDLR_DELAYPROP
Definition: cons_and.c:96
static SCIP_RETCODE consdataCatchEvents(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr)
Definition: cons_and.c:296
static SCIP_DECL_CONSGETVARS(consGetVarsAnd)
Definition: cons_and.c:4897
Constraint handler for AND constraints, .
Constraint handler for linear constraints in their most general form, .
Constraint handler for logicor constraints (equivalent to set covering, but algorithms are suited fo...
constraint handler for pseudoboolean constraints
#define ARTIFICIALVARNAMEPREFIX
Constraint handler for the set partitioning / packing / covering constraints .
methods for debugging
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#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 MAX(x, y)
Definition: def.h:239
#define SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
#define SCIP_CALL_FINALLY(x, y)
Definition: def.h:416
product expression handler
variable expression handler
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 SCIPchgAndConsCheckFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5324
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5248
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5199
SCIP_RETCODE SCIPchgAndConsRemovableFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition: cons_and.c:5355
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9409
SCIP_RETCODE SCIPsortAndCons(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5295
SCIP_Bool SCIPisAndConsSorted(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5271
SCIP_RETCODE SCIPcreateConsLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateConsSetpart(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_setppc.c:9351
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition: cons_and.c:5223
SCIP_RETCODE SCIPcreateConsLogicor(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPcreateConsBasicAnd(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *resvar, int nvars, SCIP_VAR **vars)
Definition: cons_and.c:5180
SCIP_RETCODE SCIPincludeConshdlrAnd(SCIP *scip)
Definition: cons_and.c:4982
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:711
SCIP_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_var.c:390
SCIP_RETCODE SCIPcreateExprProduct(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real coefficient, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
void SCIPgmlWriteNode(FILE *file, unsigned int id, const char *label, const char *nodetype, const char *fillcolor, const char *bordercolor)
Definition: misc.c:497
void SCIPgmlWriteClosing(FILE *file)
Definition: misc.c:699
void SCIPgmlWriteOpening(FILE *file, SCIP_Bool directed)
Definition: misc.c:683
void SCIPgmlWriteArc(FILE *file, unsigned int source, unsigned int target, const char *label, const char *color)
Definition: misc.c:639
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 SCIPgetNIntVars(SCIP *scip)
Definition: scip_prob.c:2082
int SCIPgetNImplVars(SCIP *scip)
Definition: scip_prob.c:2127
int SCIPgetNContVars(SCIP *scip)
Definition: scip_prob.c:2172
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
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
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3192
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
#define SCIPhashFour(a, b, c, d)
Definition: pub_misc.h:556
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
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 SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_RETCODE 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 SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITPRE((*consinitpre)))
Definition: scip_cons.c:492
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 SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDEACTIVE((*consdeactive)))
Definition: scip_cons.c:693
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETPERMSYMGRAPH((*consgetpermsymgraph)))
Definition: scip_cons.c:900
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSEXITPRE((*consexitpre)))
Definition: scip_cons.c:516
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH((*consgetsignedpermsymgraph)))
Definition: scip_cons.c:924
SCIP_RETCODE 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_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSACTIVE((*consactive)))
Definition: scip_cons.c:670
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8244
int SCIPconsGetPos(SCIP_CONS *cons)
Definition: cons.c:8224
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 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 SCIPconsIsAdded(SCIP_CONS *cons)
Definition: cons.c:8643
SCIP_RETCODE SCIPupdateConsFlags(SCIP *scip, SCIP_CONS *cons0, SCIP_CONS *cons1)
Definition: scip_cons.c:1525
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
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1417
#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_RETCODE SCIPdelNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition: scip_nlp.c:424
SCIP_RETCODE SCIPaddNlRow(SCIP *scip, SCIP_NLROW *nlrow)
Definition: scip_nlp.c:396
SCIP_Bool SCIPisNLPConstructed(SCIP *scip)
Definition: scip_nlp.c:110
SCIP_RETCODE SCIPreleaseNlRow(SCIP *scip, SCIP_NLROW **nlrow)
Definition: scip_nlp.c:1058
SCIP_Bool SCIPnlrowIsInNLP(SCIP_NLROW *nlrow)
Definition: nlp.c:1956
SCIP_RETCODE SCIPcreateNlRow(SCIP *scip, SCIP_NLROW **nlrow, const char *name, SCIP_Real constant, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, SCIP_EXPR *expr, SCIP_Real lhs, SCIP_Real rhs, SCIP_EXPRCURV curvature)
Definition: scip_nlp.c:954
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
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 SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition: scip_tree.c:146
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
Definition: scip_tree.c:434
SCIP_NODE * SCIPgetRootNode(SCIP *scip)
Definition: scip_tree.c:110
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition: scip_var.c:4351
void SCIPvarsGetProbvar(SCIP_VAR **vars, int nvars)
Definition: var.c:12198
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17894
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
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_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3353
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition: scip_var.c:8565
SCIP_RETCODE SCIPvarGetAggregatedObj(SCIP_VAR *var, SCIP_Real *aggrobj)
Definition: var.c:17948
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPgetBinvarRepresentatives(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **repvars, SCIP_Bool *negated)
Definition: scip_var.c:1644
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_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition: var.c:12218
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:533
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17758
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
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition: scip_var.c:8176
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_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17574
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
int SCIPvarCompare(SCIP_VAR *var1, SCIP_VAR *var2)
Definition: var.c:11942
SCIP_RETCODE SCIPvarGetProbvarBinary(SCIP_VAR **var, SCIP_Bool *negated)
Definition: var.c:12310
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_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition: var.c:11475
int SCIPvarGetNLocksDownType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition: var.c:3295
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1439
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8629
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
memory allocation routines
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:134
#define BMSclearMemoryArray(ptr, num)
Definition: memory.h:130
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public methods for managing constraints
public methods for managing events
public methods for LP management
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
#define SCIPdebug(x)
Definition: pub_message.h:93
#define SCIPdebugPrintCons(x, y, z)
Definition: pub_message.h:102
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for problem variables
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
public functions to work with algebraic expressions
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for nonlinear relaxation
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for the branch-and-bound tree
public methods for SCIP variables
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
#define SCIP_DECL_CONSEXITPRE(x)
Definition: type_cons.h:180
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_EXPRCURV_UNKNOWN
Definition: type_expr.h:62
@ 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_WRITEERROR
Definition: type_retcode.h:46
@ 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_EXITPRESOLVE
Definition: type_set.h:50
@ 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
#define SCIP_PRESOLTIMING_EXHAUSTIVE
Definition: type_timing.h:54
@ SCIP_VARTYPE_INTEGER
Definition: type_var.h:63
@ SCIP_VARTYPE_IMPLINT
Definition: type_var.h:64
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_FIXED
Definition: type_var.h:52
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97