SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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 */
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 */
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
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 {
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];
850
851 if( SCIPvarGetLbGlobal(var) > 0.5 )
852 {
854 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
855 (*nchgcoefs)++;
856 }
857 else
858 {
860 SCIP_Bool negated;
861
862 /* get binary representative of variable */
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 {
884 SCIP_Bool negated;
885
886 /* get binary representative of variable */
887 SCIP_CALL( SCIPgetBinvarRepresentative(scip, consdata->resvar, &repvar, &negated) );
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 */
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;
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 */
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 {
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 {
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
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 */
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 solval;
1124 SCIP_Real minsolval;
1125 SCIP_Real sumsolval;
1126 SCIP_Real viol;
1127 int minsolind;
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 minsolind = 0;
1139 minsolval = 1.0;
1140 sumsolval = 0.0;
1141
1142 /* evaluate operator variables */
1143 for( i = 0; i < consdata->nvars; ++i )
1144 {
1145 solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
1146
1147 if( solval < minsolval )
1148 {
1149 minsolind = i;
1150 minsolval = solval;
1151 }
1152
1153 sumsolval += solval;
1154 }
1155
1156 /* the resultant must be at most as large as every operator
1157 * and at least as large as one minus the sum of negated operators
1158 */
1159 solval = SCIPgetSolVal(scip, sol, consdata->resvar);
1160 viol = MAX3(0.0, solval - minsolval, sumsolval - (consdata->nvars - 1.0 + solval));
1161
1162 if( SCIPisFeasPositive(scip, viol) )
1163 {
1164 *violated = TRUE;
1165
1166 /* only reset constraint age if we are in enforcement */
1167 if( sol == NULL )
1168 {
1170 }
1171
1172 if( printreason )
1173 {
1174 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
1175 SCIPinfoMessage(scip, NULL, ";\n");
1176 SCIPinfoMessage(scip, NULL, "violation:");
1177
1178 if( SCIPisFeasPositive(scip, solval - minsolval) )
1179 {
1180 SCIPinfoMessage(scip, NULL, " operand <%s> = FALSE and resultant <%s> = TRUE\n",
1181 SCIPvarGetName(consdata->vars[minsolind]), SCIPvarGetName(consdata->resvar));
1182 }
1183 else
1184 {
1185 SCIPinfoMessage(scip, NULL, " all operands are TRUE and resultant <%s> = FALSE\n",
1186 SCIPvarGetName(consdata->resvar));
1187 }
1188 }
1189 }
1190
1191 if( sol != NULL )
1192 SCIPupdateSolConsViolation(scip, sol, viol, viol);
1193 }
1194
1195 return SCIP_OKAY;
1196}
1197
1198/** separates given primal solution */
1199static
1201 SCIP* scip, /**< SCIP data structure */
1202 SCIP_CONS* cons, /**< constraint to check */
1203 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1204 SCIP_Bool* separated, /**< pointer to store whether a cut was found */
1205 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1206 )
1207{
1208 SCIP_CONSDATA* consdata;
1209 SCIP_Real feasibility;
1210 int r;
1211
1212 assert(separated != NULL);
1213 assert(cutoff != NULL);
1214
1215 *separated = FALSE;
1216 *cutoff = FALSE;
1217
1218 consdata = SCIPconsGetData(cons);
1219 assert(consdata != NULL);
1220
1221 /* create all necessary rows for the linear relaxation */
1222 if( consdata->rows == NULL )
1223 {
1225 }
1226 assert(consdata->rows != NULL);
1227
1228 /* test all rows for feasibility and add infeasible rows */
1229 for( r = 0; r < consdata->nrows; ++r )
1230 {
1231 if( !SCIProwIsInLP(consdata->rows[r]) )
1232 {
1233 feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
1235 {
1236 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, cutoff) );
1237 if ( *cutoff )
1238 return SCIP_OKAY;
1239 *separated = TRUE;
1240 }
1241 }
1242 }
1243
1244 return SCIP_OKAY;
1245}
1246
1247/** analyzes conflicting TRUE assignment to resultant of given constraint, and adds conflict constraint to problem */
1248static
1250 SCIP* scip, /**< SCIP data structure */
1251 SCIP_CONS* cons, /**< AND-constraint that detected the conflict */
1252 int falsepos /**< position of operand that is fixed to FALSE */
1253 )
1254{
1255 SCIP_CONSDATA* consdata;
1256
1257 /* conflict analysis can only be applied in solving stage and if it turned on */
1259 return SCIP_OKAY;
1260
1261 consdata = SCIPconsGetData(cons);
1262 assert(consdata != NULL);
1263 assert(SCIPvarGetLbLocal(consdata->resvar) > 0.5);
1265 assert(SCIPvarGetUbLocal(consdata->vars[falsepos]) < 0.5);
1266
1267 /* initialize conflict analysis, and add resultant and single operand variable to conflict candidate queue */
1269
1270 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1271 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[falsepos]) );
1272
1273 /* analyze the conflict */
1275
1276 return SCIP_OKAY;
1277}
1278
1279/** analyzes conflicting FALSE assignment to resultant of given constraint, and adds conflict constraint to problem */
1280static
1282 SCIP* scip, /**< SCIP data structure */
1283 SCIP_CONS* cons /**< or constraint that detected the conflict */
1284 )
1285{
1286 SCIP_CONSDATA* consdata;
1287 int v;
1288
1290
1291 /* conflict analysis can only be applied in solving stage and if it is applicable */
1293 return SCIP_OKAY;
1294
1295 consdata = SCIPconsGetData(cons);
1296 assert(consdata != NULL);
1297 assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1298
1299 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
1301
1302 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1303 for( v = 0; v < consdata->nvars; ++v )
1304 {
1305 assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1306 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->vars[v]) );
1307 }
1308
1309 /* analyze the conflict */
1311
1312 return SCIP_OKAY;
1313}
1314
1315/** tries to fix the given resultant to zero */
1316static
1318 SCIP* scip, /**< SCIP data structure */
1319 SCIP_CONS* cons, /**< AND-constraint to be processed */
1320 SCIP_VAR* resvar, /**< resultant variable to fix to zero */
1321 int pos, /**< position of operand that is fixed to FALSE */
1322 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1323 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1324 )
1325{
1326 SCIP_Bool infeasible;
1327 SCIP_Bool tightened;
1328
1329 SCIPdebugMsg(scip, "constraint <%s>: operator %d fixed to 0.0 -> fix resultant <%s> to 0.0\n",
1330 SCIPconsGetName(cons), pos, SCIPvarGetName(resvar));
1331
1332 SCIP_CALL( SCIPinferBinvarCons(scip, resvar, FALSE, cons, (int)PROPRULE_1, &infeasible, &tightened) );
1333
1334 if( infeasible )
1335 {
1336 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1337 SCIP_CALL( analyzeConflictOne(scip, cons, pos) );
1339 (*cutoff) = TRUE;
1340 }
1341 else
1342 {
1344 if( tightened )
1345 {
1347 (*nfixedvars)++;
1348 }
1349 }
1350
1351 return SCIP_OKAY;
1352}
1353
1354/** fix all operands to one */
1355static
1357 SCIP* scip, /**< SCIP data structure */
1358 SCIP_CONS* cons, /**< AND-constraint to be processed */
1359 SCIP_VAR** vars, /**< array of operands */
1360 int nvars, /**< number of operands */
1361 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1362 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1363 )
1364{
1365 SCIP_Bool infeasible;
1366 SCIP_Bool tightened;
1367 int v;
1368
1369 for( v = 0; v < nvars && !(*cutoff); ++v )
1370 {
1371 SCIPdebugMsg(scip, "constraint <%s>: resultant fixed to 1.0 -> fix operator var <%s> to 1.0\n",
1373
1374 SCIP_CALL( SCIPinferBinvarCons(scip, vars[v], TRUE, cons, (int)PROPRULE_2, &infeasible, &tightened) );
1375
1376 if( infeasible )
1377 {
1378 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1379 SCIP_CALL( analyzeConflictOne(scip, cons, v) );
1381 (*cutoff) = TRUE;
1382 }
1383 else if( tightened )
1384 {
1386 (*nfixedvars)++;
1387 }
1388 }
1389
1390 if( !(*cutoff) )
1391 {
1393 }
1394
1395 return SCIP_OKAY;
1396}
1397
1398/** linearize AND-constraint due to a globally to zero fixed resultant; that is, creates, adds, and releases a logicor
1399 * constraint and remove the AND-constraint globally.
1400 *
1401 * Since the resultant is fixed to zero the AND-constraint collapses to linear constraint of the form:
1402 *
1403 * - \f$\sum_{i=0}^{n-1} v_i \leq n-1\f$
1404 *
1405 * This can be transformed into a logicor constraint of the form
1406 *
1407 * - \f$\sum_{i=0}^{n-1} ~v_i \geq 1\f$
1408 */
1409static
1411 SCIP* scip, /**< SCIP data structure */
1412 SCIP_CONS* cons, /**< AND-constraint to linearize */
1413 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1414 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1415 int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1416 )
1417{
1418 SCIP_CONSDATA* consdata;
1419 SCIP_VAR** vars;
1420 SCIP_CONS* lincons;
1421 SCIP_Bool conscreated;
1422 int nvars;
1423
1424 consdata = SCIPconsGetData(cons);
1425 assert(consdata != NULL);
1426
1427 assert(!(*cutoff));
1428 assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
1429
1430 nvars = consdata->nvars;
1432
1433 /* allocate memory for variables for updated constraint */
1435
1436 /* if we only have two variables, we prefer a set packing constraint instead of a logicor constraint */
1437 if( nvars == 2 && !SCIPconsIsModifiable(cons) )
1438 {
1439 SCIP_Bool* negated;
1440 SCIP_Bool infeasible;
1441 SCIP_Bool tightened;
1442
1443 /* get active representation */
1447
1448 /* if one of the two operators is globally fixed to one it follows that the other has to be zero */
1449 if( SCIPvarGetLbGlobal(vars[0]) > 0.5 )
1450 {
1451 SCIP_CALL( SCIPfixVar(scip, vars[1], 0.0, &infeasible, &tightened) );
1452
1453 if( infeasible )
1454 *cutoff = TRUE;
1455 else if( tightened )
1456 ++(*nfixedvars);
1457 }
1458 else if( SCIPvarGetLbGlobal(vars[1]) > 0.5 )
1459 {
1460 SCIP_CALL( SCIPfixVar(scip, vars[0], 0.0, &infeasible, &tightened) );
1461
1462 if( infeasible )
1463 *cutoff = TRUE;
1464 else if( tightened )
1465 ++(*nfixedvars);
1466 }
1467 else if( SCIPvarGetUbGlobal(vars[0]) > 0.5 && SCIPvarGetUbGlobal(vars[1]) > 0.5 )
1468 {
1469 /* create, add, and release the setppc constraint */
1472 consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1474 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1475
1476 conscreated = TRUE;
1477 }
1478 }
1479 else
1480 {
1481 int v;
1482
1483 /* collect negated variables */
1484 for( v = 0; v < nvars; ++v )
1485 {
1486 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &vars[v]) );
1487 }
1488
1489 /* create, add, and release the logicor constraint */
1492 consdata->checkwhenupgr || SCIPconsIsChecked(cons),
1494 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1495
1496 conscreated = TRUE;
1497 }
1498
1499 if( conscreated )
1500 {
1501 /* add and release new constraint */
1502 SCIPdebugPrintCons(scip, lincons, NULL); /*lint !e644*/
1503 SCIP_CALL( SCIPaddCons(scip, lincons) ); /*lint !e644*/
1504 SCIP_CALL( SCIPreleaseCons(scip, &lincons) ); /*lint !e644*/
1505
1506 ++(*nupgdconss);
1507 }
1508
1509 /* remove the AND-constraint globally */
1510 SCIP_CALL( SCIPdelCons(scip, cons) );
1511
1512 /* delete temporary memory */
1514
1515 return SCIP_OKAY;
1516}
1517
1518/** the resultant is fixed to zero; in case all except one operator are fixed to TRUE the last operator has to fixed to FALSE */
1519/** @note consdata->watchedvars might not be the same to the watchedvar parameters, because the update was not yet done */
1520static
1522 SCIP* scip, /**< SCIP data structure */
1523 SCIP_CONS* cons, /**< AND-constraint to be processed */
1524 int watchedvar1, /**< maybe last unfixed variable position */
1525 int watchedvar2, /**< second watched position */
1526 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1527 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1528 )
1529{
1530 SCIP_CONSDATA* consdata;
1531
1532 consdata = SCIPconsGetData(cons);
1533 assert(consdata != NULL);
1534 assert(SCIPvarGetUbLocal(consdata->resvar) < 0.5);
1535
1536 if( watchedvar2 == -1 )
1537 {
1538 SCIP_Bool infeasible;
1539 SCIP_Bool tightened;
1540
1541 assert(watchedvar1 != -1);
1542
1543#ifndef NDEBUG
1544 /* check that all variables regardless of wathcedvar1 are fixed to 1 */
1545 {
1546 int v;
1547
1548 for( v = consdata->nvars - 1; v >= 0; --v )
1549 if( v != watchedvar1 )
1550 assert(SCIPvarGetLbLocal(consdata->vars[v]) > 0.5);
1551 }
1552#endif
1553
1554 SCIPdebugMsg(scip, "constraint <%s>: resultant <%s> fixed to 0.0, only one unfixed operand -> fix operand <%s> to 0.0\n",
1555 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar), SCIPvarGetName(consdata->vars[watchedvar1]));
1556
1557 SCIP_CALL( SCIPinferBinvarCons(scip, consdata->vars[watchedvar1], FALSE, cons, (int)PROPRULE_4, &infeasible, &tightened) );
1558
1559 if( infeasible )
1560 {
1561 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1564 *cutoff = TRUE;
1565 }
1566 else
1567 {
1569 if( tightened )
1570 {
1572 (*nfixedvars)++;
1573 }
1574 }
1575 }
1576
1577 return SCIP_OKAY;
1578}
1579
1580/** replaces multiple occurrences of variables */
1581static
1583 SCIP* scip, /**< SCIP data structure */
1584 SCIP_CONS* cons, /**< AND-constraint */
1585 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1586 unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
1587 int* nentries, /**< pointer for array size, if array will be to small it's corrected */
1588 int* nfixedvars, /**< pointer to store number of fixed variables */
1589 int* nchgcoefs, /**< pointer to store number of changed coefficients */
1590 int* ndelconss /**< pointer to store number of deleted constraints */
1591 )
1592{
1593 SCIP_CONSDATA* consdata;
1594 SCIP_VAR** vars;
1595 SCIP_VAR* var;
1597 int probidx;
1598 int nvars;
1599 int v;
1600#ifndef NDEBUG
1601 int nbinvars;
1602 int nintvars;
1603 int nimplvars;
1604#endif
1605
1606 assert(scip != NULL);
1607 assert(cons != NULL);
1608 assert(eventhdlr != NULL);
1609 assert(*entries != NULL);
1610 assert(nentries != NULL);
1611 assert(nfixedvars != NULL);
1612 assert(nchgcoefs != NULL);
1613 assert(ndelconss != NULL);
1614
1615 consdata = SCIPconsGetData(cons);
1616 assert(consdata != NULL);
1617
1618 if( consdata->merged )
1619 return SCIP_OKAY;
1620
1621 /* nothing to merge */
1622 if( consdata->nvars <= 1 )
1623 {
1624 consdata->merged = TRUE;
1625 return SCIP_OKAY;
1626 }
1627
1628 vars = consdata->vars;
1629 nvars = consdata->nvars;
1630
1631 assert(vars != NULL);
1632 assert(nvars >= 2);
1633
1634#ifndef NDEBUG
1637 nimplvars = SCIPgetNImplVars(scip);
1638 assert(*nentries >= nbinvars + nintvars + nimplvars);
1639#endif
1640
1641 /* initialize entries array */
1642 for( v = nvars - 1; v >= 0; --v )
1643 {
1644 var = vars[v];
1645 assert(var != NULL);
1647
1649 assert(probvar != NULL);
1650
1652 assert(0 <= probidx);
1653
1654 /* check variable type, either pure binary or an integer/implicit integer variable with 0/1 bounds */
1656 || (SCIPvarIsBinary(probvar) &&
1658 (probidx >= nbinvars + nintvars && probidx < nbinvars + nintvars + nimplvars &&
1660
1661 /* var is not active yet */
1662 (*entries)[probidx] = 0;
1663 }
1664
1665 /* search for multiple variables; scan from back to front because deletion doesn't affect the order of the front
1666 * variables
1667 * @note don't reorder variables because we would loose the watched variables and filter position inforamtion
1668 */
1669 for( v = nvars - 1; v >= 0; --v )
1670 {
1671 var = vars[v];
1672 assert(var != NULL);
1674
1676 assert(probvar != NULL);
1677
1679 assert(0 <= probidx && probidx < *nentries);
1680
1681 /* if var occurs first time in constraint init entries array */
1682 if( (*entries)[probidx] == 0 )
1683 {
1684 (*entries)[probidx] = (SCIPvarIsActive(var) ? 1 : 2);
1685 }
1686 /* if var occurs second time in constraint, first time it was not negated */
1687 else if( ((*entries)[probidx] == 1 && SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && !SCIPvarIsActive(var)) )
1688 {
1689 /* delete the multiple variable */
1690 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1691 ++(*nchgcoefs);
1692 }
1693 else
1694 {
1695 SCIP_Bool infeasible;
1696 SCIP_Bool fixed;
1697
1698 assert(((*entries)[probidx] == 1 && !SCIPvarIsActive(var)) || ((*entries)[probidx] == 2 && SCIPvarIsActive(var)));
1699
1700 SCIPdebugMsg(scip, "AND-constraint <%s> is redundant: variable <%s> and its negation are present -> fix resultant <%s> = 0\n",
1701 SCIPconsGetName(cons), SCIPvarGetName(var), SCIPvarGetName(consdata->resvar));
1702
1703 /* negation of the variable is already present in the constraint: fix resultant to zero */
1704#ifndef NDEBUG
1705 {
1706 int i;
1707 for( i = consdata->nvars - 1; i > v && var != SCIPvarGetNegatedVar(vars[i]); --i )
1708 {}
1709 assert(i > v);
1710 }
1711#endif
1712
1713 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
1714 assert(!infeasible);
1715 if( fixed )
1716 ++(*nfixedvars);
1717
1718 SCIP_CALL( SCIPdelCons(scip, cons) );
1719 break;
1720 }
1721 }
1722
1723 consdata->merged = TRUE;
1724
1725 return SCIP_OKAY;
1726}
1727
1728/** propagates constraint with the following rules:
1729 * (1) v_i = FALSE => r = FALSE
1730 * (2) r = TRUE => v_i = TRUE for all i
1731 * (3) v_i = TRUE for all i => r = TRUE
1732 * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1733 *
1734 * additional if the resultant is fixed to zero during presolving or in the root node (globally), then the
1735 * AND-constraint is collapsed to a linear (logicor) constraint of the form
1736 * -> sum_{i=0}^{n-1} ~v_i >= 1
1737 */
1738static
1740 SCIP* scip, /**< SCIP data structure */
1741 SCIP_CONS* cons, /**< AND-constraint to be processed */
1742 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1743 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1744 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1745 int* nupgdconss /**< pointer to add up the number of upgraded constraints */
1746 )
1747{
1748 SCIP_CONSDATA* consdata;
1749 SCIP_VAR* resvar;
1750 SCIP_VAR** vars;
1751 int nvars;
1752 int watchedvar1;
1753 int watchedvar2;
1754 int i;
1755 SCIP_Bool infeasible;
1756 SCIP_Bool tightened;
1757
1758 assert(cutoff != NULL);
1759 assert(nfixedvars != NULL);
1760
1761 consdata = SCIPconsGetData(cons);
1762 assert(consdata != NULL);
1763
1764 resvar = consdata->resvar;
1765 vars = consdata->vars;
1766 nvars = consdata->nvars;
1767
1768 /* don't process the constraint, if none of the operator variables was fixed to FALSE, and if the watched variables
1769 * and the resultant weren't fixed to any value since last propagation call
1770 */
1771 if( consdata->propagated )
1772 {
1773 assert(consdata->nofixedzero);
1774 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(resvar), 0.0));
1775 return SCIP_OKAY;
1776 }
1777
1778 /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
1780 {
1781 SCIP_CALL( SCIPincConsAge(scip, cons) );
1782 }
1783
1784 /* if one of the operator variables was fixed to FALSE, the resultant can be fixed to FALSE (rule (1)) */
1785 if( !consdata->nofixedzero )
1786 {
1787 for( i = 0; i < nvars && SCIPvarGetUbLocal(vars[i]) > 0.5; ++i ) /* search for operator fixed to zero */
1788 {}
1789 if( i < nvars )
1790 {
1791 /* fix resultant to zero */
1792 SCIP_CALL( consdataFixResultantZero(scip, cons, resvar, i, cutoff, nfixedvars) );
1793 }
1794 else
1795 consdata->nofixedzero = TRUE;
1796 }
1797
1798 /* check if resultant variables is globally fixed to zero */
1799 if( !SCIPinProbing(scip) && SCIPvarGetUbGlobal(resvar) < 0.5 )
1800 {
1801 SCIP_CALL( consdataLinearize(scip, cons, cutoff, nfixedvars, nupgdconss) );
1802
1803 if( *cutoff && SCIPgetDepth(scip) > 0 )
1804 {
1805 /* we are done with solving since a global bound change was infeasible */
1807 }
1808
1809 return SCIP_OKAY;
1810 }
1811
1812 /* if the resultant and at least one operand are locally fixed to zero, the constraint is locally redundant */
1813 if( SCIPvarGetUbLocal(resvar) < 0.5 && !consdata->nofixedzero )
1814 {
1816 return SCIP_OKAY;
1817 }
1818
1819 /* if resultant is fixed to TRUE, all operator variables can be fixed to TRUE (rule (2)) */
1820 if( SCIPvarGetLbLocal(resvar) > 0.5 )
1821 {
1822 /* fix operands to one */
1823 SCIP_CALL( consdataFixOperandsOne(scip, cons, vars, nvars, cutoff, nfixedvars) );
1824
1825 return SCIP_OKAY;
1826 }
1827
1828 /* rules (3) and (4) can only be applied, if we know all operator variables */
1829 if( SCIPconsIsModifiable(cons) )
1830 return SCIP_OKAY;
1831
1832 /* rules (3) and (4) cannot be applied, if we have at least two unfixed variables left;
1833 * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
1834 * if these ones get fixed
1835 */
1836 watchedvar1 = consdata->watchedvar1;
1837 watchedvar2 = consdata->watchedvar2;
1838
1839 /* check, if watched variables are still unfixed */
1840 if( watchedvar1 != -1 )
1841 {
1842 assert(SCIPvarGetUbLocal(vars[watchedvar1]) > 0.5); /* otherwise, rule (1) could be applied */
1843 if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 )
1844 watchedvar1 = -1;
1845 }
1846 if( watchedvar2 != -1 )
1847 {
1848 assert(SCIPvarGetUbLocal(vars[watchedvar2]) > 0.5); /* otherwise, rule (1) could be applied */
1849 if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 )
1850 watchedvar2 = -1;
1851 }
1852
1853 /* if only one watched variable is still unfixed, make it the first one */
1854 if( watchedvar1 == -1 )
1855 {
1856 watchedvar1 = watchedvar2;
1857 watchedvar2 = -1;
1858 }
1859 assert(watchedvar1 != -1 || watchedvar2 == -1);
1860
1861 /* if the watched variables are invalid (fixed), find new ones if existing */
1862 if( watchedvar2 == -1 )
1863 {
1864 for( i = 0; i < nvars; ++i )
1865 {
1866 assert(SCIPvarGetUbLocal(vars[i]) > 0.5); /* otherwise, rule (1) could be applied */
1867 if( SCIPvarGetLbLocal(vars[i]) < 0.5 )
1868 {
1869 if( watchedvar1 == -1 )
1870 {
1871 assert(watchedvar2 == -1);
1872 watchedvar1 = i;
1873 }
1874 else if( watchedvar1 != i )
1875 {
1876 watchedvar2 = i;
1877 break;
1878 }
1879 }
1880 }
1881 }
1882 assert(watchedvar1 != -1 || watchedvar2 == -1);
1883
1884 /* if all variables are fixed to TRUE, the resultant can also be fixed to TRUE (rule (3)) */
1885 if( watchedvar1 == -1 )
1886 {
1887 assert(watchedvar2 == -1);
1888
1889 SCIPdebugMsg(scip, "constraint <%s>: all operator vars fixed to 1.0 -> fix resultant <%s> to 1.0\n",
1890 SCIPconsGetName(cons), SCIPvarGetName(resvar));
1891 SCIP_CALL( SCIPinferBinvarCons(scip, resvar, TRUE, cons, (int)PROPRULE_3, &infeasible, &tightened) );
1892
1893 if( infeasible )
1894 {
1895 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1898 *cutoff = TRUE;
1899 }
1900 else
1901 {
1903 if( tightened )
1904 {
1906 (*nfixedvars)++;
1907 }
1908 }
1909
1910 return SCIP_OKAY;
1911 }
1912
1913 /* if resultant is fixed to FALSE, and only one operator variable is not fixed to TRUE, this operator variable
1914 * can be fixed to FALSE (rule (4))
1915 */
1916 if( watchedvar2 == -1 && SCIPvarGetUbLocal(resvar) < 0.5 )
1917 {
1918 assert(watchedvar1 != -1);
1919
1920 SCIP_CALL( analyzeZeroResultant(scip, cons, watchedvar1, watchedvar2, cutoff, nfixedvars) );
1921
1922 return SCIP_OKAY;
1923 }
1924
1925 /* switch to the new watched variables */
1926 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
1927
1928 /* mark the constraint propagated if we have an unfixed resultant or are not in probing, it is necessary that a fixed
1929 * resulting in probing mode does not lead to a propagated constraint, because the constraint upgrade needs to be performed
1930 */
1931 consdata->propagated = (!SCIPinProbing(scip) || (SCIPvarGetLbLocal(consdata->resvar) < 0.5 && SCIPvarGetUbLocal(consdata->resvar) > 0.5));
1932
1933 return SCIP_OKAY;
1934}
1935
1936/** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
1937 * propagation rule (see propagateCons()):
1938 * (1) v_i = FALSE => r = FALSE
1939 * (2) r = TRUE => v_i = TRUE for all i
1940 * (3) v_i = TRUE for all i => r = TRUE
1941 * (4) r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
1942 */
1943static
1945 SCIP* scip, /**< SCIP data structure */
1946 SCIP_CONS* cons, /**< constraint that inferred the bound change */
1947 SCIP_VAR* infervar, /**< variable that was deduced */
1948 PROPRULE proprule, /**< propagation rule that deduced the value */
1949 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1950 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1951 )
1952{
1953 SCIP_CONSDATA* consdata;
1954 SCIP_VAR** vars;
1955 int nvars;
1956 int i;
1957
1958 assert(result != NULL);
1959
1960 consdata = SCIPconsGetData(cons);
1961 assert(consdata != NULL);
1962 vars = consdata->vars;
1963 nvars = consdata->nvars;
1964
1965 switch( proprule )
1966 {
1967 case PROPRULE_1:
1968 /* the resultant was inferred to FALSE, because one operand variable was FALSE */
1969 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
1970 assert(infervar == consdata->resvar);
1971 for( i = 0; i < nvars; ++i )
1972 {
1973 if( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
1974 {
1976 break;
1977 }
1978 }
1979 assert(i < nvars);
1981 break;
1982
1983 case PROPRULE_2:
1984 /* the operand variable was inferred to TRUE, because the resultant was TRUE */
1985 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1986 assert(SCIPgetVarLbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) > 0.5);
1987 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
1989 break;
1990
1991 case PROPRULE_3:
1992 /* the resultant was inferred to TRUE, because all operand variables were TRUE */
1993 assert(SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE) > 0.5);
1994 assert(infervar == consdata->resvar);
1995 for( i = 0; i < nvars; ++i )
1996 {
1997 assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
1999 }
2001 break;
2002
2003 case PROPRULE_4:
2004 /* the operand variable was inferred to FALSE, because the resultant was FALSE and all other operands were TRUE */
2005 assert(SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE) < 0.5);
2006 assert(SCIPgetVarUbAtIndex(scip, consdata->resvar, bdchgidx, FALSE) < 0.5);
2007 SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->resvar) );
2008 for( i = 0; i < nvars; ++i )
2009 {
2010 if( vars[i] != infervar )
2011 {
2012 assert(SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5);
2014 }
2015 }
2017 break;
2018
2019 case PROPRULE_INVALID:
2020 default:
2021 SCIPerrorMessage("invalid inference information %d in AND-constraint <%s>\n", proprule, SCIPconsGetName(cons));
2022 return SCIP_INVALIDDATA;
2023 }
2024
2025 return SCIP_OKAY;
2026}
2027
2028/** perform dual presolving on AND-constraints */
2029static
2031 SCIP* scip, /**< SCIP data structure */
2032 SCIP_CONS** conss, /**< AND-constraints to perform dual presolving on */
2033 int nconss, /**< number of AND-constraints */
2034 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2035 unsigned char** entries, /**< array to store whether two positions in constraints represent the same variable */
2036 int* nentries, /**< pointer for array size, if array will be to small it's corrected */
2037 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2038 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
2039 int* naggrvars, /**< pointer to add up the number of aggregated variables */
2040 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
2041 int* ndelconss, /**< pointer to add up the number of deleted constraints */
2042 int* nupgdconss, /**< pointer to add up the number of upgraded constraints */
2043 int* naddconss /**< pointer to add up the number of added constraints */
2044 )
2045{
2046 SCIP_CONS* cons;
2047 SCIP_CONSDATA* consdata;
2049 SCIP_VAR** vars;
2050 SCIP_VAR* resvar;
2051 SCIP_VAR* var;
2052 int nimpoperands;
2053 int nvars;
2054 int size;
2055 int v;
2056 int c;
2057 SCIP_Bool infeasible;
2058 SCIP_Bool fixed;
2059
2060 assert(scip != NULL);
2061 assert(conss != NULL || nconss == 0);
2062 assert(eventhdlr != NULL);
2063 assert(*entries != NULL);
2064 assert(nentries != NULL);
2065 assert(cutoff != NULL);
2066 assert(nfixedvars != NULL);
2067 assert(naggrvars != NULL);
2068 assert(nchgcoefs != NULL);
2069 assert(ndelconss != NULL);
2070 assert(nupgdconss != NULL);
2071 assert(naddconss != NULL);
2072
2073 if( nconss == 0 )
2074 return SCIP_OKAY;
2075
2076 assert(conss != NULL);
2077
2078 size = 2 * (SCIPgetNBinVars(scip) + SCIPgetNImplVars(scip));
2079
2081
2082 for( c = nconss - 1; c >= 0 && !(*cutoff); --c )
2083 {
2084 cons = conss[c];
2085 assert(cons != NULL);
2086
2087 if( !SCIPconsIsActive(cons) || !SCIPconsIsChecked(cons) || SCIPconsIsModifiable(cons) )
2088 continue;
2089
2090 /* propagate constraint */
2091 SCIP_CALL( propagateCons(scip, cons, eventhdlr, cutoff, nfixedvars, nupgdconss) );
2092
2093 if( !SCIPconsIsActive(cons) )
2094 continue;
2095
2096 if( *cutoff )
2097 break;
2098
2099 SCIP_CALL( applyFixings(scip, cons, eventhdlr, nchgcoefs) );
2100
2101 /* merge multiple occurances of variables or variables with their negated variables */
2102 SCIP_CALL( mergeMultiples(scip, cons, eventhdlr, entries, nentries, nfixedvars, nchgcoefs, ndelconss) );
2103
2104 if( !SCIPconsIsActive(cons) )
2105 continue;
2106
2107 consdata = SCIPconsGetData(cons);
2108 assert(consdata != NULL);
2109
2110 vars = consdata->vars;
2111 nvars = consdata->nvars;
2112 assert(vars != NULL || nvars == 0);
2113
2114 if( nvars == 0 )
2115 continue;
2116
2117 assert(vars != NULL);
2118
2119 resvar = consdata->resvar;
2120 assert(resvar != NULL);
2121 /* a fixed resultant needs to be removed, otherwise we might fix operands to a wrong value later on */
2122 assert(SCIPvarGetLbGlobal(resvar) < 0.5 && SCIPvarGetUbGlobal(resvar) > 0.5);
2125
2128 {
2129 SCIP_Real resobj;
2130 SCIP_Real obj;
2131 SCIP_Real posobjsum = 0;
2132 SCIP_Real maxobj = -SCIPinfinity(scip);
2133 int maxpos = -1;
2134 int oldnfixedvars = *nfixedvars;
2135 int oldnaggrvars = *naggrvars;
2136
2137 nimpoperands = 0;
2138
2139 /* collect important operands */
2140 for( v = nvars - 1; v >= 0; --v )
2141 {
2142 var = vars[v];
2143 assert(var != NULL);
2146
2149 {
2151 ++nimpoperands;
2152
2153 /* get aggregated objective value of active variable */
2155
2156 /* add up all positive objective values of operands which have exactly one lock in both directions */
2157 if( obj > 0 )
2158 posobjsum += obj;
2159
2160 /* memorize maximal objective value of operands and its position */
2161 if( obj > maxobj )
2162 {
2163 maxpos = nimpoperands - 1;
2164 maxobj = obj;
2165 }
2166 }
2167 }
2169
2170 /* no dual fixable variables found */
2171 if( nimpoperands == 0 )
2172 continue;
2173
2174 /* get aggregated objective value of active variable */
2176
2177 /* resultant contributes to the objective with a negative value */
2178 if( SCIPisLE(scip, resobj, 0.0) )
2179 {
2181
2182 /* if all variables are only locked by this constraint and the resultants contribution more then compensates
2183 * the positive contribution, we can fix all variables to 1
2184 */
2186 {
2187 SCIPdebugMsg(scip, "dual-fixing all variables in constraint <%s> to 1\n", SCIPconsGetName(cons));
2188
2189 SCIP_CALL( SCIPfixVar(scip, resvar, 1.0, &infeasible, &fixed) );
2190
2191 *cutoff = *cutoff || infeasible;
2192 if( fixed )
2193 ++(*nfixedvars);
2194
2195 for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2196 {
2197 SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2198
2199 *cutoff = *cutoff || infeasible;
2200 if( fixed )
2201 ++(*nfixedvars);
2202 }
2203
2204 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed to one\n", SCIPconsGetName(cons));
2205
2206 SCIP_CALL( SCIPdelCons(scip, cons) );
2207 ++(*ndelconss);
2208 }
2209 else
2210 {
2211 SCIP_Bool aggregationperformed = FALSE;
2212 SCIP_Bool zerofix = FALSE;
2213
2214 assert(nimpoperands > 0);
2215
2216 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));
2217
2218 for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2219 {
2220 /* get aggregated objective value of active variable */
2222
2223 if( SCIPisLE(scip, obj, 0.0) )
2224 {
2225 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2226
2227 *cutoff = *cutoff || infeasible;
2228 if( fixed )
2229 ++(*nfixedvars);
2230 }
2231 else if( !poscontissmall )
2232 {
2233 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2234 assert(!infeasible);
2235 assert(fixed);
2236
2237 ++(*nfixedvars);
2238 zerofix = TRUE;
2239 }
2240 else
2241 {
2242 SCIP_Bool redundant;
2243 SCIP_Bool aggregated;
2244
2245 /* aggregate resultant to operand */
2246 SCIP_CALL( SCIPaggregateVars(scip, resvar, impoperands[v], 1.0, -1.0, 0.0,
2247 &infeasible, &redundant, &aggregated) );
2248 assert(!infeasible);
2249
2250 if( aggregated )
2251 {
2252 /* note that we cannot remove the aggregated operand because we do not know the position */
2253 ++(*naggrvars);
2254
2256
2257 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));
2258 }
2259 }
2260 }
2261 assert(*nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars <= nimpoperands);
2262
2263 /* did we aggregate the resultant, then we can decide the value to fix it on the (aggregated) objective
2264 * value since it was a independant variable
2265 */
2267 {
2268 SCIP_Real fixval;
2269
2270 if( zerofix )
2271 fixval = 0.0;
2272 else
2273 {
2274 /* get aggregated objective value of active variable, that might be changed */
2277
2278 fixval = (SCIPisNegative(scip, obj) ? 1.0 : 0.0);
2279 }
2280
2281 if( fixval < 0.5 || *nfixedvars - oldnfixedvars + *naggrvars - oldnaggrvars == nvars )
2282 {
2283 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);
2284
2285 SCIP_CALL( SCIPfixVar(scip, resvar, fixval, &infeasible, &fixed) );
2286 assert(!infeasible);
2287 assert(fixed);
2288
2289 ++(*nfixedvars);
2290
2291 SCIPdebugMsg(scip, "deleting constraint <%s> because \n", SCIPconsGetName(cons));
2292
2293 SCIP_CALL( SCIPdelCons(scip, cons) );
2294 ++(*ndelconss);
2295 }
2296 }
2297 }
2298 }
2299 /* resultant contributes to the objective with a positive value */
2300 else
2301 {
2302 SCIP_Bool zerofix = FALSE;
2303#ifndef NDEBUG
2304 SCIP_Real tmpobj;
2305
2306 assert(nimpoperands > 0);
2311#endif
2312
2313 /* if the smallest possible contribution is negative, but does not compensate the positive contribution of
2314 * the resultant we need to fix this variable to 0
2315 */
2316 if( nimpoperands == nvars && SCIPisLE(scip, maxobj, 0.0) )
2317 {
2318 SCIP_Real fixval = (SCIPisLE(scip, REALABS(maxobj), resobj) ? 0.0 : 1.0);
2319
2320 SCIPdebugMsg(scip, "dual-fixing variable <%s> in constraint <%s> to %g, because the contribution is%s " \
2321 "enough to nullify/exceed the contribution of the resultant \n",
2322 SCIPvarGetName(impoperands[maxpos]), SCIPconsGetName(cons), fixval, (fixval < 0.5) ? " not" : "");
2323
2324 SCIP_CALL( SCIPfixVar(scip, impoperands[maxpos], fixval, &infeasible, &fixed) );
2325 zerofix = (fixval < 0.5);
2326
2327 *cutoff = *cutoff || infeasible;
2328 if( fixed )
2329 ++(*nfixedvars);
2330 }
2331
2332 SCIPdebugMsg(scip, "dual-fixing all variables, except the variable with the highest contribution to " \
2333 "the objective, in constraint <%s> with positive contribution to 0 and with negative contribution to 1\n",
2334 SCIPconsGetName(cons));
2335
2336 for( v = nimpoperands - 1; v >= 0 && !(*cutoff); --v )
2337 {
2338 /* get aggregated objective value of active variable */
2340
2341 if( SCIPisLE(scip, obj, 0.0) )
2342 {
2343 if( v == maxpos )
2344 continue;
2345
2346 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 1.0, &infeasible, &fixed) );
2347 }
2348 else
2349 {
2350 SCIP_CALL( SCIPfixVar(scip, impoperands[v], 0.0, &infeasible, &fixed) );
2351 zerofix = TRUE;
2352 }
2353
2354 *cutoff = *cutoff || infeasible;
2355 if( fixed )
2356 ++(*nfixedvars);
2357 }
2358 assert(*nfixedvars - oldnfixedvars <= nimpoperands);
2359 /* iff we have fixed all variables, all variables needed to be stored in the impoperands array */
2360 assert((*nfixedvars - oldnfixedvars == nvars) == (nimpoperands == nvars));
2361
2362 if( *nfixedvars - oldnfixedvars == nvars )
2363 {
2364 SCIPdebugMsg(scip, "all operands are fixed in constraint <%s> => fix resultant <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(resvar), (zerofix ? 0.0 : 1.0));
2365
2366 SCIP_CALL( SCIPfixVar(scip, resvar, zerofix ? 0.0 : 1.0, &infeasible, &fixed) );
2367
2368 *cutoff = *cutoff || infeasible;
2369 if( fixed )
2370 ++(*nfixedvars);
2371
2372 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are fixed\n", SCIPconsGetName(cons));
2373
2374 SCIP_CALL( SCIPdelCons(scip, cons) );
2375 ++(*ndelconss);
2376 }
2377 }
2378 }
2379 /* resultant is lock by another constraint (handler), check for operands with only one down- and uplock */
2380 else
2381 {
2382 SCIP_Real maxobj = -SCIPinfinity(scip);
2383 SCIP_Real resobj;
2384 SCIP_Real obj;
2385 SCIP_Bool redundant;
2386 SCIP_Bool aggregated;
2387 SCIP_Bool resobjispos;
2388 SCIP_Bool linearize = FALSE;
2389 SCIP_Bool zerofix = FALSE;
2390#ifndef NDEBUG
2391 int oldnchgcoefs = *nchgcoefs;
2392 int oldnfixedvars = *nfixedvars;
2393#endif
2394
2395 /* get aggregated objective value of active variable */
2397
2399
2400 /* we can only aggregate when the objective contribution of the resultant is less or equal to 0 */
2401 if( !resobjispos )
2402 {
2403 SCIP_Bool goodvarsfound = FALSE;
2404
2405 for( v = nvars - 1; v >= 0; --v )
2406 {
2407 var = vars[v];
2408 assert(var != NULL);
2411
2412 /* get aggregated objective value of active variable */
2414
2415 /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2416 * to 0 can be aggregated to the resultant
2417 */
2420 {
2421 if( !SCIPisNegative(scip, obj) )
2422 {
2423 /* aggregate resultant to operand */
2424 SCIP_CALL( SCIPaggregateVars(scip, resvar, var, 1.0, -1.0, 0.0, &infeasible, &redundant,
2425 &aggregated) );
2426
2427 if( aggregated )
2428 {
2429 ++(*naggrvars);
2430
2431 linearize = TRUE;
2432
2433 /* delete redundant entry from constraint */
2434 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2435 ++(*nchgcoefs);
2436
2438 "dual aggregating operand <%s> with 1 up- and downlock to the resultant <%s> in constraint <%s>\n",
2440 }
2441
2442 *cutoff = *cutoff || infeasible;
2443 }
2444 else
2446 }
2447 }
2448 assert(*nchgcoefs - oldnchgcoefs <= nvars);
2449
2450 /* if we aggregated an operands with the resultant we can also fix "good" independant operands to 1, since
2451 * the correctness of "resultant = 0 => at least one operand = 0" in enforced by that aggregation
2452 * without an aggregation we cannot fix these variables since it might lead to infeasibility, e.g.
2453 *
2454 * obj(x3) = -1
2455 * r = x1 * x2 * x3
2456 * r = 0
2457 * x1 = 1
2458 * x2 = 1
2459 */
2460 if( !*cutoff && goodvarsfound && linearize )
2461 {
2462 /* fix good variables to 1 */
2463 for( v = consdata->nvars - 1; v >= 0; --v )
2464 {
2465 var = vars[v];
2466 assert(var != NULL);
2467
2470 {
2471#ifndef NDEBUG
2472 /* aggregated objective value of active variable need to be negative */
2475#endif
2477 "dual-fixing variable <%s> in constraint <%s> to 1, because the contribution is negative\n",
2479
2480 SCIP_CALL( SCIPfixVar(scip, var, 1.0, &infeasible, &fixed) );
2481
2482 assert(!infeasible);
2483 if( fixed )
2484 ++(*nfixedvars);
2485 }
2486 }
2488 }
2489 assert(*nchgcoefs - oldnchgcoefs + *nfixedvars - oldnfixedvars <= nvars);
2490 }
2491 /* if the downlocks of the resultant are only from this constraint and the objective contribution is positive,
2492 * we can try to fix operands
2493 */
2494 else if( SCIPvarGetNLocksDownType(resvar, SCIP_LOCKTYPE_MODEL) == 1 )
2495 {
2496 SCIP_Bool locksareone = TRUE;
2497 int maxpos = -1;
2498
2499 for( v = nvars - 1; v >= 0; --v )
2500 {
2501 var = vars[v];
2502 assert(var != NULL);
2505
2506 /* check if all resultants are only locked by this constraint */
2509
2510 /* get aggregated objective value of active variable */
2512
2513 /* memorize maximal objective value of operands and its position */
2514 if( obj > maxobj )
2515 {
2516 maxpos = v;
2517 maxobj = obj;
2518 }
2519
2520 /* all operands which are only locked by this constraint, the objective contribution is greater or equal
2521 * to 0, and the absolute value of the contribution of the resultant exceeds can be eliminated and
2522 * aggregated to the resultant
2523 */
2526 {
2527 SCIPdebugMsg(scip, "dualfix operand <%s> in constraint <%s> to 0\n", SCIPvarGetName(var), SCIPconsGetName(cons));
2528
2529 SCIP_CALL( SCIPfixVar(scip, var, 0.0, &infeasible, &fixed) );
2530
2531 *cutoff = *cutoff || infeasible;
2532 if( fixed )
2533 ++(*nfixedvars);
2534
2535 zerofix = TRUE;
2536 }
2537 }
2538 assert(*nchgcoefs - oldnchgcoefs <= nvars);
2539
2540 /* if constraint is still active and all operands are only lock by this constraint, we check if we can fix
2541 * the worst (in objective contribution) operand to zero
2542 */
2544 {
2545 assert(!zerofix);
2546 /* objective contribution needs to be negative, otherwise, the variable should already be fixed to 0 */
2547 assert(SCIPisLT(scip, maxobj, 0.0));
2548
2549 SCIPdebugMsg(scip, "dualfix operand <%s> with worst contribution in constraint <%s> to 0\n", SCIPvarGetName(vars[maxpos]), SCIPconsGetName(cons));
2550
2551 SCIP_CALL( SCIPfixVar(scip, vars[maxpos], 0.0, &infeasible, &fixed) );
2552
2553 *cutoff = *cutoff || infeasible;
2554 if( fixed )
2555 ++(*nfixedvars);
2556
2557 zerofix = TRUE;
2558 }
2559
2560 /* fix the resultant if one operand was fixed to zero and delete the constraint */
2561 if( zerofix )
2562 {
2563 SCIPdebugMsg(scip, "fix resultant <%s> in constraint <%s> to 0\n", SCIPvarGetName(resvar), SCIPconsGetName(cons));
2564
2565 SCIP_CALL( SCIPfixVar(scip, resvar, 0.0, &infeasible, &fixed) );
2566
2567 *cutoff = *cutoff || infeasible;
2568 if( fixed )
2569 ++(*nfixedvars);
2570
2571 SCIPdebugMsg(scip, "deleting constraint <%s> because at least one operand and the resultant is fixed to zero\n", SCIPconsGetName(cons));
2572
2573 SCIP_CALL( SCIPdelCons(scip, cons) );
2574 ++(*ndelconss);
2575 }
2576 }
2577
2578 /* we have to linearize the constraint, otherwise we might get wrong propagations, since due to aggregations a
2579 * resultant fixed to zero is already fulfilling the constraint, and we must not ensure that some remaining
2580 * operand needs to be 0
2581 */
2582 if( linearize )
2583 {
2585 char consname[SCIP_MAXSTRLEN];
2586 SCIP_VAR* consvars[2];
2587 SCIP_Real vals[2];
2588
2589 assert(SCIPconsIsActive(cons));
2590
2591 consvars[0] = consdata->resvar;
2592 vals[0] = 1.0;
2593 vals[1] = -1.0;
2594
2595 /* create operator linear constraints */
2596 for( v = consdata->nvars - 1; v >= 0; --v )
2597 {
2598 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
2599 consvars[1] = consdata->vars[v];
2600
2601 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, consvars, vals, -SCIPinfinity(scip), 0.0,
2605 SCIPconsIsStickingAtNode(cons)) );
2606
2607 /* add constraint */
2610 }
2611 (*naddconss) += consdata->nvars;
2612
2613 SCIPdebugMsg(scip, "deleting constraint <%s> because it was linearized\n", SCIPconsGetName(cons));
2614
2615 SCIP_CALL( SCIPdelCons(scip, cons) );
2616 ++(*ndelconss);
2617 }
2618 /* if only one operand is leftover, aggregate it to the resultant */
2619 else if( consdata->nvars == 1 )
2620 {
2621 SCIPdebugMsg(scip, "aggregating last operand <%s> to the resultant <%s> in constraint <%s>\n", SCIPvarGetName(consdata->vars[0]), SCIPvarGetName(resvar), SCIPconsGetName(cons));
2622
2623 /* aggregate resultant to operand */
2624 SCIP_CALL( SCIPaggregateVars(scip, resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2625 &infeasible, &redundant, &aggregated) );
2626
2627 if( aggregated )
2628 ++(*naggrvars);
2629
2630 *cutoff = *cutoff || infeasible;
2631
2632 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2633
2634 SCIP_CALL( SCIPdelCons(scip, cons) );
2635 ++(*ndelconss);
2636 }
2637
2638 /* if no operand is leftover delete the constraint */
2639 if( SCIPconsIsActive(cons) && consdata->nvars == 0 )
2640 {
2641 SCIPdebugMsg(scip, "deleting constraint <%s> because all variables are removed\n", SCIPconsGetName(cons));
2642
2643 SCIP_CALL( SCIPdelCons(scip, cons) );
2644 ++(*ndelconss);
2645 }
2646 }
2647 }
2648
2650
2651 return SCIP_OKAY;
2652}
2653
2654/** 1. check if at least two operands or one operand and the resultant are in one clique, if so, we can fix the
2655 * resultant to zero and in the former case we can also delete this constraint but we need to extract the clique
2656 * information as constraint
2657 *
2658 * x == AND(y, z) and clique(y,z) => x = 0, delete constraint and create y + z <= 1
2659 * x == AND(y, z) and clique(x,y) => x = 0
2660 *
2661 * special handled cases are:
2662 * - if the resultant is a negation of an operand, in that case we fix the resultant to 0
2663 * - if the resultant is equal to an operand, we will linearize this constraint by adding all necessary
2664 * set-packing constraints like resultant + ~operand <= 1 and delete the old constraint
2665 *
2666 * x == AND(~x, y) => x = 0
2667 * x == AND(x, y) => add x + ~y <= 1 and delete the constraint
2668 *
2669 * 2. check if one operand is in a clique with the negation of all other operands, this means we can aggregate this
2670 * operand to the resultant
2671 *
2672 * r == AND(x,y,z) and clique(x,~y) and clique(x,~z) => r == x
2673 *
2674 * 3. check if the resultant and the negations of all operands are in a clique
2675 *
2676 * r == AND(x,y) and clique(r, ~x,~y) => upgrade the constraint to a set-partitioning constraint r + ~x + ~y = 1
2677 *
2678 * @note We removed also fixed variables and propagate them, and if only one operand is remaining due to removal, we
2679 * will aggregate the resultant with this operand
2680 */
2681static
2683 SCIP* scip, /**< SCIP data structure */
2684 SCIP_CONS* cons, /**< constraint to process */
2685 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2686 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2687 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
2688 int* naggrvars, /**< pointer to add up the number of aggregated variables */
2689 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
2690 int* ndelconss, /**< pointer to add up the number of deleted constraints */
2691 int* naddconss /**< pointer to add up the number of added constraints */
2692 )
2693{
2694 SCIP_CONSDATA* consdata;
2695 SCIP_VAR** vars;
2696 SCIP_VAR* var1;
2697 SCIP_VAR* var2;
2698 int nvars;
2699 int vstart;
2700 int vend;
2701 int v;
2702 int v2;
2703 SCIP_Bool negated;
2704 SCIP_Bool value1;
2705 SCIP_Bool value2;
2706 SCIP_Bool infeasible;
2707 SCIP_Bool fixed;
2708 SCIP_Bool allnegoperandsexist;
2709
2710 assert(scip != NULL);
2711 assert(cons != NULL);
2712 assert(eventhdlr != NULL);
2713 assert(cutoff != NULL);
2714 assert(nfixedvars != NULL);
2715 assert(naggrvars != NULL);
2716 assert(nchgcoefs != NULL);
2717 assert(ndelconss != NULL);
2718 assert(naddconss != NULL);
2719
2720 consdata = SCIPconsGetData(cons);
2721 assert(consdata != NULL);
2722
2723 if( !SCIPconsIsActive(cons) || SCIPconsIsModifiable(cons) )
2724 return SCIP_OKAY;
2725
2726 vars = consdata->vars;
2727 nvars = consdata->nvars;
2728 assert(vars != NULL || nvars == 0);
2729
2730 /* remove fixed variables to be able to ask for cliques
2731 *
2732 * if an operand is fixed to 0 fix the resultant to 0 and delete the constraint
2733 * if an operand is fixed to 1 remove it from the constraint
2734 */
2735 for( v = nvars - 1; v >= 0; --v )
2736 {
2737 assert(vars != NULL);
2738
2739 if( SCIPvarGetLbGlobal(vars[v]) > 0.5 )
2740 {
2741 SCIPdebugMsg(scip, "In constraint <%s> the operand <%s> is fixed to 1 so remove it from the constraint\n",
2743
2744 /* because we loop from back to front we can delete the entry in the consdata structure */
2745 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
2746 ++(*nchgcoefs);
2747
2748 assert(consdata->vars == vars);
2749
2750 continue;
2751 }
2752 else if( SCIPvarGetUbGlobal(vars[v]) < 0.5 )
2753 {
2754 SCIPdebugMsg(scip, "constraint <%s> redundant: because operand <%s> is fixed to zero so we can fix the resultant <%s> to 0\n",
2755 SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
2756
2757 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2758 *cutoff = *cutoff || infeasible;
2759 if( fixed )
2760 ++(*nfixedvars);
2761
2762 SCIP_CALL( SCIPdelCons(scip, cons) );
2763 ++(*ndelconss);
2764
2765 return SCIP_OKAY;
2766 }
2767 }
2768
2769 /* if we deleted some operands constraint might be redundant */
2770 if( consdata->nvars < nvars )
2771 {
2772 assert(vars == consdata->vars);
2773
2774 /* all operands fixed to one were removed, so if no operand is left this means we can fix the resultant to 1
2775 * too
2776 */
2777 if( consdata->nvars == 0 )
2778 {
2779 SCIPdebugMsg(scip, "All operand in constraint <%s> were deleted, so the resultant needs to be fixed to 1\n",
2780 SCIPconsGetName(cons));
2781
2782 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 1.0, &infeasible, &fixed) );
2783 *cutoff = *cutoff || infeasible;
2784 if( fixed )
2785 ++(*nfixedvars);
2786
2787 SCIP_CALL( SCIPdelCons(scip, cons) );
2788 ++(*ndelconss);
2789
2790 return SCIP_OKAY;
2791 }
2792 /* if only one not fixed operand is left, we can aggregate it to the resultant */
2793 else if( consdata->nvars == 1 )
2794 {
2795 SCIP_Bool redundant;
2796 SCIP_Bool aggregated;
2797
2798 /* aggregate resultant to last operand */
2799 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
2800 &infeasible, &redundant, &aggregated) );
2801
2802 if( aggregated )
2803 ++(*naggrvars);
2804
2805 SCIP_CALL( SCIPdelCons(scip, cons) );
2806 ++(*ndelconss);
2807
2808 *cutoff = *cutoff || infeasible;
2809
2810 return SCIP_OKAY;
2811 }
2812
2813 nvars = consdata->nvars;
2814 }
2815
2816 /* @todo when cliques are improved, we only need to collect all clique-ids for all variables and check for doubled
2817 * entries
2818 */
2819 /* case 1 first part */
2820 /* check if two operands are in a clique */
2821 for( v = nvars - 1; v > 0; --v )
2822 {
2823 assert(vars != NULL);
2824
2825 var1 = vars[v];
2826 assert(var1 != NULL);
2827 negated = FALSE;
2828
2830 assert(var1 != NULL);
2831
2832 if( negated )
2833 value1 = FALSE;
2834 else
2835 value1 = TRUE;
2836
2838
2839 for( v2 = v - 1; v2 >= 0; --v2 )
2840 {
2841 var2 = vars[v2];
2842 assert(var2 != NULL);
2843
2844 negated = FALSE;
2846 assert(var2 != NULL);
2847
2848 if( negated )
2849 value2 = FALSE;
2850 else
2851 value2 = TRUE;
2852
2854
2855 /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2856 * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better
2857 * continue
2858 */
2859 if( var1 == var2 )
2860 continue;
2861
2863 {
2865 SCIP_VAR* consvars[2];
2866 char name[SCIP_MAXSTRLEN];
2867
2868 SCIPdebugMsg(scip, "constraint <%s> redundant: because variable <%s> and variable <%s> are in a clique, the resultant <%s> can be fixed to 0\n",
2870
2871 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2872 *cutoff = *cutoff || infeasible;
2873 if( fixed )
2874 ++(*nfixedvars);
2875
2876 /* create clique constraint which lead to the last fixing */
2877 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%d", SCIPconsGetName(cons), v2);
2878
2879 if( value1 )
2880 consvars[0] = var1;
2881 else
2882 {
2883 SCIP_CALL( SCIPgetNegatedVar(scip, var1, &(consvars[0])) );
2884 }
2885
2886 if( value2 )
2887 consvars[1] = var2;
2888 else
2889 {
2890 SCIP_CALL( SCIPgetNegatedVar(scip, var2, &(consvars[1])) );
2891 }
2892
2893 SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
2895 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2897 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
2898 SCIPdebugMsg(scip, " -> adding clique constraint: ");
2902 ++(*naddconss);
2903
2904 SCIP_CALL( SCIPdelCons(scip, cons) );
2905 ++(*ndelconss);
2906
2907 return SCIP_OKAY;
2908 }
2909 }
2910 }
2911
2912 var1 = consdata->resvar;
2913 assert(var1 != NULL);
2914
2915 negated = FALSE;
2917 assert(var1 != NULL);
2918
2919 /* it may appear that we have a fixed resultant */
2921 {
2922 /* resultant is fixed to 1, so fix all operands to 1 */
2923 if( SCIPvarGetLbGlobal(consdata->resvar) > 0.5 )
2924 {
2925 SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> is fixed to 1 so fix all operands to 1\n",
2926 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2927
2928 /* fix all operands to 1 */
2929 for( v = nvars - 1; v >= 0 && !(*cutoff); --v )
2930 {
2931 assert(vars != NULL);
2932
2933 SCIPdebugMsg(scip, "Fixing operand <%s> to 1.\n", SCIPvarGetName(vars[v]));
2934
2935 SCIP_CALL( SCIPfixVar(scip, vars[v], 1.0, &infeasible, &fixed) );
2936 *cutoff = *cutoff || infeasible;
2937
2938 if( fixed )
2939 ++(*nfixedvars);
2940 }
2941
2942 SCIP_CALL( SCIPdelCons(scip, cons) );
2943 ++(*ndelconss);
2944 }
2945 /* the upgrade to a linear constraint because of the to 0 fixed resultant we do in propagateCons() */
2946 else
2947 assert(SCIPvarGetUbGlobal(consdata->resvar) < 0.5);
2948
2949 return SCIP_OKAY;
2950 }
2951
2952 if( negated )
2953 value1 = FALSE;
2954 else
2955 value1 = TRUE;
2956
2957 /* case 1 second part */
2958 /* check if one operands is in a clique with the resultant */
2959 for( v = nvars - 1; v >= 0; --v )
2960 {
2961 assert(vars != NULL);
2962
2963 var2 = vars[v];
2964 assert(var2 != NULL);
2965
2966 negated = FALSE;
2968 assert(var2 != NULL);
2969
2970 if( negated )
2971 value2 = FALSE;
2972 else
2973 value2 = TRUE;
2974
2975 /* if both variables are negated of each other or the same, this will be handled in applyFixings();
2976 * @note if both variables are the same, then SCIPvarsHaveCommonClique() will return TRUE, so we better continue
2977 */
2978 if( var1 == var2 )
2979 {
2980 /* x1 == AND(~x1, x2 ...) => x1 = 0 */
2981 if( value1 != value2 )
2982 {
2983 SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
2984 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
2985
2986 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
2987 *cutoff = *cutoff || infeasible;
2988
2989 if( fixed )
2990 ++(*nfixedvars);
2991
2992 return SCIP_OKAY;
2993 }
2994 /* x1 == AND(x1, x2 ...) => delete constraint and create all set-packing constraints x1 + ~x2 <= 1, x1 + ~... <= 1 */
2995 else
2996 {
2998 SCIP_VAR* consvars[2];
2999 char name[SCIP_MAXSTRLEN];
3000
3001 assert(value1 == value2);
3002
3003 consvars[0] = consdata->resvar;
3004
3005 for( v2 = nvars - 1; v2 >= 0; --v2 )
3006 {
3007 var2 = vars[v2];
3008 negated = FALSE;
3010
3011 /* if the active representations of the resultant and an operand are different then we need to extract
3012 * this as a clique constraint
3013 *
3014 * if the active representations of the resultant and an operand are equal then the clique constraint
3015 * would look like x1 + ~x1 <= 1, which is redundant
3016 *
3017 * if the active representations of the resultant and an operand are negated of each other then the
3018 * clique constraint would look like x1 + x1 <= 1, which will lead to a fixation of the resultant later
3019 * on
3020 */
3021 if( var1 == var2 )
3022 {
3023 if( value1 == negated )
3024 {
3025 SCIPdebugMsg(scip, "In constraint <%s> the resultant <%s> can be fixed to 0 because the negation of it is an operand.\n",
3026 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
3027
3028 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3029 *cutoff = *cutoff || infeasible;
3030
3031 if( fixed )
3032 ++(*nfixedvars);
3033
3034 break;
3035 }
3036 }
3037 else
3038 {
3039 SCIP_CALL( SCIPgetNegatedVar(scip, vars[v2], &consvars[1]) );
3040 assert(consvars[1] != NULL);
3041
3042 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clq_%d", SCIPconsGetName(cons), v2);
3043
3044 SCIP_CALL( SCIPcreateConsSetpack(scip, &cliquecons, name, 2, consvars,
3046 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
3048 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3049 SCIPdebugMsg(scip, " -> adding clique constraint: ");
3053 ++(*naddconss);
3054 }
3055 }
3056
3057 /* delete old constraint */
3058 SCIP_CALL( SCIPdelCons(scip, cons) );
3059 ++(*ndelconss);
3060
3061 return SCIP_OKAY;
3062 }
3063 }
3064
3065 /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
3066 * it explicitly
3067 */
3068 if( var1 == var2 && value1 == value2 )
3069 continue;
3070
3071 /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
3072 * handle it explicitly
3073 */
3075 {
3076 SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because it is in a clique with operand <%s>\n",
3078
3079 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3080 *cutoff = *cutoff || infeasible;
3081 if( fixed )
3082 ++(*nfixedvars);
3083
3084 return SCIP_OKAY;
3085 }
3086 }
3087
3088 if( !SCIPconsIsActive(cons) )
3089 return SCIP_OKAY;
3090
3091 v2 = -1;
3092 /* check which operands have a negated variable */
3093 for( v = nvars - 1; v >= 0; --v )
3094 {
3095 assert(vars != NULL);
3096
3097 var1 = vars[v];
3098 assert(var1 != NULL);
3099
3100 negated = FALSE;
3102 assert(var1 != NULL);
3103
3105 {
3106 if( v2 >= 0 )
3107 break;
3108 v2 = v;
3109 }
3110 }
3111
3113
3114 /* all operands have a negated variable, so we will check for all possible negated ciques */
3115 if( v2 == -1 )
3116 {
3118 vstart = nvars - 1;
3119 vend = 0;
3120 }
3121 /* exactly one operands has no negated variable, so only this variable can be in a clique with all other negations */
3122 else if( v2 >= 0 && v == -1 )
3123 {
3124 vstart = v2;
3125 vend = v2;
3126 }
3127 /* at least two operands have no negated variable, so there is no possible clique with negated variables */
3128 else
3129 {
3130 vstart = -1;
3131 vend = 0;
3132 }
3133
3134 /* case 2 */
3135 /* check for negated cliques in the operands */
3136 for( v = vstart; v >= vend; --v )
3137 {
3138 assert(vars != NULL);
3139
3140 var1 = vars[v];
3141 assert(var1 != NULL);
3142
3143 negated = FALSE;
3145 assert(var1 != NULL);
3146
3147 if( negated )
3148 value1 = FALSE;
3149 else
3150 value1 = TRUE;
3151
3152 for( v2 = nvars - 1; v2 >= 0; --v2 )
3153 {
3154 if( v2 == v )
3155 continue;
3156
3157 var2 = vars[v2];
3158 assert(var2 != NULL);
3159
3160 negated = FALSE;
3162 assert(var2 != NULL);
3163
3164 if( negated )
3165 value2 = FALSE;
3166 else
3167 value2 = TRUE;
3168
3170
3171 /* invert flag, because we want to check var 1 against all negations of the other variables */
3172 value2 = !value2;
3173
3174 /* due to SCIPvarsHaveCommonClique() returns on two same variables that they are in a clique, we need to handle
3175 * it explicitly
3176 */
3177 if( var1 == var2 && value1 == value2 )
3178 {
3179 SCIPdebugMsg(scip, "in constraint <%s> the resultant <%s> can be fixed to 0 because two operands are negated of each other\n",
3180 SCIPconsGetName(cons), SCIPvarGetName(consdata->resvar));
3181
3182 SCIP_CALL( SCIPfixVar(scip, consdata->resvar, 0.0, &infeasible, &fixed) );
3183 *cutoff = *cutoff || infeasible;
3184 if( fixed )
3185 ++(*nfixedvars);
3186
3187 return SCIP_OKAY;
3188 }
3189
3190 /* due to SCIPvarsHaveCommonClique() returns on two negated variables that they are not in a clique, we need to
3191 * handle it explicitly
3192 */
3193 if( var1 == var2 && value1 != value2 )
3194 continue;
3195
3197 break;
3198 }
3199
3200 if( v2 == -1 )
3201 {
3202 SCIP_Bool redundant;
3203 SCIP_Bool aggregated;
3204
3205 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",
3206 SCIPconsGetName(cons), SCIPvarGetName(vars[v]), SCIPvarGetName(consdata->resvar));
3207
3208 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, vars[v], 1.0, -1.0, 0.0,
3209 &infeasible, &redundant, &aggregated) );
3210 *cutoff = *cutoff || infeasible;
3211
3212 if( aggregated )
3213 ++(*naggrvars);
3214
3215 return SCIP_OKAY;
3216 }
3217 }
3218
3219 /* case 3 */
3220 /* check if the resultant and the negations of the operands are in a clique, then we can upgrade this constraint to a
3221 * set-partitioning constraint
3222 */
3224 {
3225 SCIP_VAR** newvars;
3226 SCIP_Bool* negations;
3227 SCIP_Bool upgrade;
3228
3229 SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars + 1) );
3232
3233 var1 = consdata->resvar;
3235 assert(var1 != NULL);
3237
3238 newvars[nvars] = var1;
3239
3240 /* get active variables */
3241 for( v = nvars - 1; v >= 0; --v )
3242 {
3243 assert(vars != NULL);
3244
3245 var1 = vars[v];
3247 assert(var1 != NULL);
3249
3250 newvars[v] = var1;
3251
3252 /* there should be no variable left that is equal or negated to the resultant */
3253 assert(newvars[v] != newvars[nvars]);
3254 }
3255
3256 upgrade = TRUE;
3257
3258 /* the resultant is in a clique with the negations of all operands, due to this AND-constraint */
3259 /* only check if the negations of all operands are in a clique */
3260 for( v = nvars - 1; v >= 0 && upgrade; --v )
3261 {
3262 for( v2 = v - 1; v2 >= 0; --v2 )
3263 {
3264 /* the resultant need to be in a clique with the negations of all operands */
3265 if( !SCIPvarsHaveCommonClique(newvars[v], negations[v], newvars[v2], negations[v2], TRUE) )
3266 {
3267 upgrade = FALSE;
3268 break;
3269 }
3270 }
3271 }
3272
3273 /* all variables are in a clique, so upgrade thi AND-constraint */
3274 if( upgrade )
3275 {
3277 char name[SCIP_MAXSTRLEN];
3278
3279 /* get new constraint variables */
3280 if( negations[nvars] )
3281 {
3282 /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3283 * (e.g. resultant = ~x = 1 - x and x = y = newvars[nvars] and negations[nvars] = TRUE,
3284 * then y does not need to have a negated variable, yet)
3285 */
3286 SCIP_CALL( SCIPgetNegatedVar(scip, newvars[nvars], &(newvars[nvars])) );
3287 }
3288 assert(newvars[nvars] != NULL);
3289
3290 for( v = nvars - 1; v >= 0; --v )
3291 {
3292 if( !negations[v] )
3293 {
3294 /* negation does not need to be existing, so SCIPvarGetNegatedVar() cannot be called
3295 * (e.g. vars[v] = ~x = 1 - x and x = y = newvars[v] and negations[v] = TRUE,
3296 * then y does not need to have a negated variable, yet)
3297 */
3298 SCIP_CALL( SCIPgetNegatedVar(scip, newvars[v], &(newvars[v])) );
3299 }
3300 assert(newvars[v] != NULL);
3301 }
3302
3303 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_clqeq", SCIPconsGetName(cons));
3304
3305 SCIP_CALL( SCIPcreateConsSetpart(scip, &cliquecons, name, nvars + 1, newvars,
3307 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3309 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3310 SCIPdebugMsg(scip, " -> upgrading AND-constraint <%s> with use of clique information to a set-partitioning constraint: \n", SCIPconsGetName(cons));
3314 ++(*naddconss);
3315
3316 /* delete old constraint */
3317 SCIP_CALL( SCIPdelCons(scip, cons) );
3318 ++(*ndelconss);
3319 }
3320
3322 SCIPfreeBufferArray(scip, &newvars);
3323 }
3324
3325 return SCIP_OKAY;
3326}
3327
3328/** gets the key of the given element */
3329static
3331{ /*lint --e{715}*/
3332 /* the key is the element itself */
3333 return elem;
3334}
3335
3336/** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
3337static
3339{
3342 SCIP_Bool coefsequal;
3343 int i;
3344#ifndef NDEBUG
3345 SCIP* scip;
3346
3347 scip = (SCIP*)userptr;
3348 assert(scip != NULL);
3349#endif
3350
3353
3354 /* checks trivial case */
3355 if( consdata1->nvars != consdata2->nvars )
3356 return FALSE;
3357
3358 /* sorts the constraints */
3361 assert(consdata1->sorted);
3362 assert(consdata2->sorted);
3363
3364 coefsequal = TRUE;
3365
3366 for( i = 0; i < consdata1->nvars ; ++i )
3367 {
3368 /* tests if variables are equal */
3369 if( consdata1->vars[i] != consdata2->vars[i] )
3370 {
3371 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
3372 SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
3373 coefsequal = FALSE;
3374 break;
3375 }
3376 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 0);
3377 }
3378
3379 return coefsequal;
3380}
3381
3382/** returns the hash value of the key */
3383static
3385{ /*lint --e{715}*/
3386 SCIP_CONSDATA* consdata;
3387 int minidx;
3388 int mididx;
3389 int maxidx;
3390
3391 consdata = SCIPconsGetData((SCIP_CONS*)key);
3392 assert(consdata != NULL);
3393 assert(consdata->sorted);
3394 assert(consdata->nvars > 0);
3395
3396 minidx = SCIPvarGetIndex(consdata->vars[0]);
3397 mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
3398 maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
3399 assert(minidx >= 0 && minidx <= maxidx);
3400
3401 return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
3402}
3403
3404/** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3405 * accordingly; in contrast to removeRedundantConstraints(), it uses a hash table
3406 */
3407static
3409 SCIP* scip, /**< SCIP data structure */
3410 BMS_BLKMEM* blkmem, /**< block memory */
3411 SCIP_CONS** conss, /**< constraint set */
3412 int nconss, /**< number of constraints in constraint set */
3413 int* firstchange, /**< pointer to store first changed constraint */
3414 SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3415 int* naggrvars, /**< pointer to count number of aggregated variables */
3416 int* ndelconss /**< pointer to count number of deleted constraints */
3417 )
3418{
3419 SCIP_HASHTABLE* hashtable;
3420 int hashtablesize;
3421 int c;
3422
3423 assert(conss != NULL);
3424 assert(ndelconss != NULL);
3425
3426 /* create a hash table for the constraint set */
3427 hashtablesize = nconss;
3428 hashtablesize = MAX(hashtablesize, HASHSIZE_ANDCONS);
3429 SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3431
3432 *cutoff = FALSE;
3433
3434 /* check all constraints in the given set for redundancy */
3435 for( c = 0; c < nconss; ++c )
3436 {
3440
3441 cons0 = conss[c];
3442
3444 continue;
3445
3447
3448 /* sort the constraint */
3450 assert(consdata0->sorted);
3451
3452 /* get constraint from current hash table with same variables as cons0 */
3453 cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3454
3455 if( cons1 != NULL )
3456 {
3458 SCIP_Bool redundant;
3459
3462
3464
3465 assert(consdata1 != NULL);
3466 assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3467
3468 assert(consdata0->sorted && consdata1->sorted);
3469 assert(consdata0->vars[0] == consdata1->vars[0]);
3470
3471 redundant = FALSE;
3472
3473 if( consdata0->resvar != consdata1->resvar )
3474 {
3475 SCIP_Bool aggregated;
3476
3477 assert(SCIPvarCompare(consdata0->resvar, consdata1->resvar) != 0);
3478
3479 /* aggregate resultants */
3480 SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3481 cutoff, &redundant, &aggregated) );
3482 assert(redundant || SCIPdoNotAggr(scip));
3483
3484 if( aggregated )
3485 ++(*naggrvars);
3486 if( *cutoff )
3487 goto TERMINATE;
3488 }
3489 else
3490 redundant = TRUE;
3491
3492 /* delete consdel */
3493 if( redundant )
3494 {
3495 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3496 /* coverity[swapped_arguments] */
3498
3499 /* also take the check when upgrade flag over if necessary */
3500 consdata1->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3501 consdata1->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3502
3504 (*ndelconss)++;
3505 }
3506
3507 /* update the first changed constraint to begin the next aggregation round with */
3508 if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3510
3512 }
3513 else
3514 {
3515 /* no such constraint in current hash table: insert cons0 into hash table */
3516 SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3517 }
3518 }
3519 TERMINATE:
3520 /* free hash table */
3521 SCIPhashtableFree(&hashtable);
3522
3523 return SCIP_OKAY;
3524}
3525
3526/** helper function to enforce constraints */
3527static
3529 SCIP* scip, /**< SCIP data structure */
3530 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3531 SCIP_CONS** conss, /**< constraints to process */
3532 int nconss, /**< number of constraints */
3533 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
3534 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
3535 )
3536{
3537 SCIP_CONSHDLRDATA* conshdlrdata;
3538 SCIP_Bool separated;
3539 SCIP_Bool violated;
3540 SCIP_Bool cutoff;
3541 int i;
3542
3543 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3544 assert(conshdlrdata != NULL);
3545
3547
3548 /* method is called only for integral solutions, because the enforcing priority is negative */
3549 for( i = 0; i < nconss; i++ )
3550 {
3551 SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
3552 if( !violated )
3553 continue;
3554
3555 if( !conshdlrdata->enforcecuts )
3556 {
3558 return SCIP_OKAY;
3559 }
3560
3561 SCIP_CALL( separateCons(scip, conss[i], sol, &separated, &cutoff) );
3562 if( cutoff )
3563 {
3565 return SCIP_OKAY;
3566 }
3567 else if( separated )
3568 {
3570 }
3571 else if( *result == SCIP_FEASIBLE ) /* do not change result separated to infeasible */
3572 {
3574 }
3575 }
3576
3577 return SCIP_OKAY;
3578}
3579
3580
3581/** compares constraint with all prior constraints for possible redundancy or aggregation,
3582 * and removes or changes constraint accordingly
3583 */
3584static
3586 SCIP* scip, /**< SCIP data structure */
3587 SCIP_CONS** conss, /**< constraint set */
3588 int firstchange, /**< first constraint that changed since last pair preprocessing round */
3589 int chkind, /**< index of constraint to check against all prior indices upto startind */
3590 SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3591 int* naggrvars, /**< pointer to count number of aggregated variables */
3592 int* nbdchgs, /**< pointer to count the number of performed bound changes, or NULL */
3593 int* ndelconss /**< pointer to count number of deleted constraints */
3594 )
3595{
3598 SCIP_Bool cons0changed;
3599 int c;
3600
3601 assert(conss != NULL);
3603 assert(cutoff != NULL);
3604 assert(naggrvars != NULL);
3605 assert(nbdchgs != NULL);
3606 assert(ndelconss != NULL);
3607
3608 /* get the constraint to be checked against all prior constraints */
3609 cons0 = conss[chkind];
3612
3614
3615 /* sort the constraint */
3617
3618 assert(consdata0->nvars >= 1);
3619 assert(consdata0->sorted);
3620
3621 /* check constraint against all prior constraints */
3622 cons0changed = consdata0->changed;
3623
3624 if( SCIPconsIsActive(cons0) )
3625 {
3626 for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff); ++c )
3627 {
3630 SCIP_Bool cons0superset;
3631 SCIP_Bool cons1superset;
3632 int v0;
3633 int v1;
3634
3635 if( c % 1000 == 0 && SCIPisStopped(scip) )
3636 break;
3637
3638 cons1 = conss[c];
3639
3640 /* ignore inactive and modifiable constraints */
3642 continue;
3643
3645 assert(consdata1 != NULL);
3646
3647#ifdef SCIP_DISABLED_CODE
3648 SCIPdebugMsg(scip, "preprocess AND-constraint pair <%s>[chg:%d] and <%s>[chg:%d]\n",
3650#endif
3651
3652 /* if both constraints were not changed since last round, we can ignore the pair */
3653 if( !cons0changed && !consdata1->changed )
3654 continue;
3655
3656 assert(consdata1->nvars >= 1);
3657
3658 /* sort the constraint */
3660 assert(consdata1->sorted);
3661
3662 /* check consdata0 against consdata1:
3663 * - if they consist of the same operands, the resultants can be aggregated
3664 * - if one operand list is a subset of the other, add implication r0 = 1 -> r1 = 1, or r1 = 1 -> r0 = 1
3665 */
3666 v0 = 0;
3667 v1 = 0;
3671 {
3672 int varcmp;
3673
3674 /* test, if variable appears in only one or in both constraints */
3676 varcmp = SCIPvarCompare(consdata0->vars[v0], consdata1->vars[v1]);
3677 else if( v0 < consdata0->nvars )
3678 varcmp = -1;
3679 else
3680 varcmp = +1;
3681
3682 switch( varcmp )
3683 {
3684 case -1:
3685 /* variable doesn't appear in consdata1 */
3687 v0++;
3688 break;
3689
3690 case +1:
3691 /* variable doesn't appear in consdata0 */
3693 v1++;
3694 break;
3695
3696 case 0:
3697 /* variable appears in both constraints */
3698 v0++;
3699 v1++;
3700 break;
3701
3702 default:
3703 SCIPerrorMessage("invalid comparison result\n");
3704 SCIPABORT();
3705 return SCIP_INVALIDDATA; /*lint !e527*/
3706 }
3707 }
3708
3709 /* check for equivalence and domination */
3711 {
3712 SCIP_Bool infeasible;
3713 SCIP_Bool redundant;
3714 SCIP_Bool aggregated;
3715
3716 /* constraints are equivalent */
3717 SCIPdebugMsg(scip, "equivalent AND-constraints <%s> and <%s>: aggregate resultants <%s> == <%s>\n",
3719 SCIPvarGetName(consdata1->resvar));
3720
3721 /* aggregate resultants */
3722 SCIP_CALL( SCIPaggregateVars(scip, consdata0->resvar, consdata1->resvar, 1.0, -1.0, 0.0,
3723 &infeasible, &redundant, &aggregated) );
3724 assert(redundant || SCIPdoNotAggr(scip));
3725
3726 if( aggregated )
3727 {
3728 assert(redundant);
3729 (*naggrvars)++;
3730 }
3731
3732 if( redundant )
3733 {
3734 /* update flags of constraint which caused the redundancy s.t. nonredundant information doesn't get lost */
3736
3737 /* also take the check when upgrade flag over if necessary */
3738 consdata0->checkwhenupgr = consdata1->checkwhenupgr || consdata0->checkwhenupgr;
3739 consdata0->notremovablewhenupgr = consdata1->notremovablewhenupgr || consdata0->notremovablewhenupgr;
3740
3741 /* delete constraint */
3743 (*ndelconss)++;
3744 }
3745
3746 *cutoff = *cutoff || infeasible;
3747 }
3748 else if( cons0superset )
3749 {
3750 SCIP_Bool infeasible;
3751 int nboundchgs;
3752
3753 /* the conjunction of cons0 is a superset of the conjunction of cons1 */
3754 SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3756 SCIPvarGetName(consdata1->resvar));
3757
3758 /* add implication */
3760 &infeasible, &nboundchgs) );
3761 *cutoff = *cutoff || infeasible;
3762 (*nbdchgs) += nboundchgs;
3763 }
3764 else if( cons1superset )
3765 {
3766 SCIP_Bool infeasible;
3767 int nboundchgs;
3768
3769 /* the conjunction of cons1 is a superset of the conjunction of cons0 */
3770 SCIPdebugMsg(scip, "AND-constraint <%s> is superset of <%s>: add implication <%s> = 1 -> <%s> = 1\n",
3772 SCIPvarGetName(consdata0->resvar));
3773
3774 /* add implication */
3776 &infeasible, &nboundchgs) );
3777 *cutoff = *cutoff || infeasible;
3778 (*nbdchgs) += nboundchgs;
3779 }
3780 }
3781 }
3782 consdata0->changed = FALSE;
3783
3784 return SCIP_OKAY;
3785}
3786
3787/** adds symmetry information of constraint to a symmetry detection graph */
3788static
3790 SCIP* scip, /**< SCIP pointer */
3791 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */
3792 SCIP_CONS* cons, /**< constraint */
3793 SYM_GRAPH* graph, /**< symmetry detection graph */
3794 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */
3795 )
3796{
3797 SCIP_CONSDATA* consdata;
3798 SCIP_VAR** andvars;
3799 SCIP_VAR** vars;
3800 SCIP_Real* vals;
3801 SCIP_Real constant = 0.0;
3802 int nlocvars;
3803 int nvars;
3804 int i;
3805
3806 assert(scip != NULL);
3807 assert(cons != NULL);
3808 assert(graph != NULL);
3809 assert(success != NULL);
3810
3811 consdata = SCIPconsGetData(cons);
3812 assert(consdata != NULL);
3813
3814 /* get active variables of the constraint */
3816 nlocvars = SCIPgetNVarsAnd(scip, cons);
3817
3820
3821 andvars = SCIPgetVarsAnd(scip, cons);
3822 for( i = 0; i < consdata->nvars; ++i )
3823 {
3824 vars[i] = andvars[i];
3825 vals[i] = 1.0;
3826 }
3827
3830 vals[nlocvars++] = 2.0;
3831 assert(nlocvars <= nvars);
3832
3833 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
3834
3836 nlocvars, cons, constant, constant, success) );
3837
3838 SCIPfreeBufferArray(scip, &vals);
3840
3841 return SCIP_OKAY;
3842}
3843
3844/*
3845 * Callback methods of constraint handler
3846 */
3847
3848/** copy method for constraint handler plugins (called when SCIP copies plugins) */
3849static
3851{ /*lint --e{715}*/
3852 assert(scip != NULL);
3853 assert(conshdlr != NULL);
3855
3856 /* call inclusion method of constraint handler */
3858
3859 *valid = TRUE;
3860
3861 return SCIP_OKAY;
3862}
3863
3864/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
3865static
3867{ /*lint --e{715}*/
3868 SCIP_CONSHDLRDATA* conshdlrdata;
3869
3870 /* free constraint handler data */
3871 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3872 assert(conshdlrdata != NULL);
3873
3874 conshdlrdataFree(scip, &conshdlrdata);
3875
3876 SCIPconshdlrSetData(conshdlr, NULL);
3877
3878 return SCIP_OKAY;
3879}
3880
3881
3882/** presolving initialization method of constraint handler (called when presolving is about to begin) */
3883static
3885{ /*lint --e{715}*/
3886 SCIP_CONSHDLRDATA* conshdlrdata;
3887
3888 assert( scip != NULL );
3889 assert( conshdlr != NULL );
3890 assert( nconss == 0 || conss != NULL );
3891
3892 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3893 assert(conshdlrdata != NULL);
3894
3895 if( conshdlrdata->linearize )
3896 {
3897 /* linearize all AND-constraints and remove the AND-constraints */
3899 SCIP_CONS* cons;
3900 SCIP_CONSDATA* consdata;
3901 char consname[SCIP_MAXSTRLEN];
3902
3903 SCIP_VAR** vars;
3904 SCIP_Real* vals;
3905
3906 int nvars;
3907 int c, v;
3908
3909 /* allocate buffer array */
3911 SCIP_CALL( SCIPallocBufferArray(scip, &vals, 2) );
3912
3913 for( c = 0; c < nconss; ++c )
3914 {
3915 cons = conss[c];
3916 assert( cons != NULL );
3917
3918 /* only added constraints can be upgraded */
3919 if( !SCIPconsIsAdded(cons) )
3920 continue;
3921
3922 consdata = SCIPconsGetData(cons);
3923 assert( consdata != NULL );
3924 assert( consdata->resvar != NULL );
3925
3926 nvars = consdata->nvars;
3927
3928 if( !conshdlrdata->aggrlinearization )
3929 {
3930 vars[0] = consdata->resvar;
3931 vals[0] = 1.0;
3932 vals[1] = -1.0;
3933
3934 /* create operator linear constraints */
3935 for( v = 0; v < nvars; ++v )
3936 {
3937 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), v);
3938 vars[1] = consdata->vars[v];
3939
3940 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, vars, vals, -SCIPinfinity(scip), 0.0,
3942 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3944 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3945
3946 /* add constraint */
3949 }
3950 }
3951
3952 /* reallocate buffer array */
3955
3956 for( v = 0; v < nvars; ++v )
3957 {
3958 vars[v] = consdata->vars[v];
3959 vals[v] = -1.0;
3960 }
3961
3962 vars[nvars] = consdata->resvar;
3963
3964 if( conshdlrdata->aggrlinearization )
3965 {
3966 /* create additional linear constraint */
3967 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_operators", SCIPconsGetName(cons));
3968
3969 vals[nvars] = (SCIP_Real) nvars;
3970
3971 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -SCIPinfinity(scip), 0.0,
3973 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3975 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3976
3977 /* add constraint */
3980 }
3981
3982 /* create additional linear constraint */
3983 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_add", SCIPconsGetName(cons));
3984
3985 vals[nvars] = 1.0;
3986
3987 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, nvars + 1, vars, vals, -nvars + 1.0, SCIPinfinity(scip),
3989 consdata->checkwhenupgr || SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
3991 !(consdata->notremovablewhenupgr) && SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
3992
3993 /* add constraint */
3996
3997 /* delete constraint */
3998 SCIP_CALL( SCIPdelCons(scip, cons) );
3999 }
4000
4001 /* free buffer array */
4003 SCIPfreeBufferArray(scip, &vals);
4004 }
4005
4006 return SCIP_OKAY;
4007}
4008
4009
4010#ifdef GMLGATEPRINTING
4011
4012/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
4013static
4015{ /*lint --e{715}*/
4016 SCIP_HASHMAP* hashmap;
4017 FILE* gmlfile;
4018 char fname[SCIP_MAXSTRLEN];
4019 SCIP_CONS* cons;
4020 SCIP_CONSDATA* consdata;
4023 int* varnodeids;
4024 SCIP_VAR** vars;
4025 int nvars;
4026 int nbinvars;
4027 int nintvars;
4028 int nimplvars;
4029 int ncontvars;
4030 int v;
4031 int c;
4032 int resid;
4033 int varid;
4034 int id = 1;
4035
4036 /* no AND-constraints available */
4037 if( nconss == 0 )
4038 return SCIP_OKAY;
4039
4041
4042 /* no variables left anymore */
4043 if( nvars == 0 )
4044 return SCIP_OKAY;
4045
4048 SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, &nintvars, &nimplvars, &ncontvars) );
4049
4050 /* open gml file */
4051 (void) SCIPsnprintf(fname, SCIP_MAXSTRLEN, "and-gates%p.gml", scip);
4052 gmlfile = fopen(fname, "w");
4053
4054 if( gmlfile == NULL )
4055 {
4056 SCIPerrorMessage("cannot open graph file <%s>\n", fname);
4057 SCIPABORT();
4058 return SCIP_WRITEERROR; /*lint !e527*/
4059 }
4060
4061 /* create the variable mapping hash map */
4063
4064 /* write starting of gml file */
4066
4067 /* walk over all AND-constraints */
4068 for( c = nconss - 1; c >= 0; --c )
4069 {
4070 cons = conss[c];
4071
4072 /* only handle active constraints */
4073 if( !SCIPconsIsActive(cons) )
4074 continue;
4075
4076 consdata = SCIPconsGetData(cons);
4077 assert(consdata != NULL);
4078
4079 /* only handle constraints which have operands */
4080 if( consdata->nvars == 0 )
4081 continue;
4082
4083 assert(consdata->vars != NULL);
4084 assert(consdata->resvar != NULL);
4085
4086 /* get active variable of resultant */
4087 activevar = SCIPvarGetProbvar(consdata->resvar);
4088
4089 /* check if we already found this variables */
4091 assert(resid >= 0);
4092
4093 if( resid == 0 )
4094 {
4095 resid = id;
4096 ++id;
4097 SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activevar, resid) );
4098
4099 /* write new gml node for new resultant */
4101 }
4102
4103 /* copy operands to get problem variables for */
4104 SCIP_CALL( SCIPduplicateBufferArray(scip, &activeconsvars, consdata->vars, consdata->nvars) );
4105
4106 /* get problem variables of operands */
4107 SCIPvarsGetProbvar(activeconsvars, consdata->nvars);
4108
4109 for( v = consdata->nvars - 1; v >= 0; --v )
4110 {
4111 /* check if we already found this variables */
4113 if( varid == 0 )
4114 {
4115 varid = id;
4116 ++id;
4117 SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4118
4119 /* write new gml node for new operand */
4121 }
4122 /* write gml arc between resultant and operand */
4124 }
4125
4126 /* free temporary memory for active constraint variables */
4128 }
4129
4130 /* write all remaining variables as nodes */
4131#ifdef SCIP_DISABLED_CODE
4132 for( v = nvars - 1; v >= 0; --v )
4133 {
4135
4137 assert(varid >= 0);
4138
4139 if( varid == 0 )
4140 {
4141 varid = id;
4142 ++id;
4143 SCIP_CALL( SCIPhashmapInsertInt(hashmap, (void*)activeconsvars[v], varid) );
4144
4145 /* write new gml node for new operand */
4147 }
4148 }
4149#endif
4150
4151 /* free the variable mapping hash map */
4152 SCIPhashmapFree(&hashmap);
4153
4155
4156 fclose(gmlfile);
4157
4160
4161 return SCIP_OKAY;
4162}
4163#endif
4164
4165/** solving process initialization method of constraint handler */
4166static
4168{ /*lint --e{715}*/
4169 /* add nlrow representation to NLP, if NLP had been constructed */
4171 {
4172 int c;
4173 for( c = 0; c < nconss; ++c )
4174 {
4175 SCIP_CALL( addNlrow(scip, conss[c]) );
4176 }
4177 }
4178
4179 return SCIP_OKAY;
4180}
4181
4182/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4183static
4185{ /*lint --e{715}*/
4186 SCIP_CONSDATA* consdata;
4187 int c;
4188
4189 /* release and free the rows and nlrow of all constraints */
4190 for( c = 0; c < nconss; ++c )
4191 {
4192 consdata = SCIPconsGetData(conss[c]);
4193 assert(consdata != NULL);
4194
4195 SCIP_CALL( consdataFreeRows(scip, consdata) );
4196
4197 if( consdata->nlrow != NULL )
4198 {
4199 SCIP_CALL( SCIPreleaseNlRow(scip, &consdata->nlrow) );
4200 }
4201 }
4202
4203 return SCIP_OKAY;
4204}
4205
4206
4207/** frees specific constraint data */
4208static
4210{ /*lint --e{715}*/
4211 SCIP_CONSHDLRDATA* conshdlrdata;
4212
4213 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4214 assert(conshdlrdata != NULL);
4215
4216 SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4217
4218 return SCIP_OKAY;
4219}
4220
4221
4222/** transforms constraint data into data belonging to the transformed problem */
4223static
4225{ /*lint --e{715}*/
4226 SCIP_CONSHDLRDATA* conshdlrdata;
4229
4230 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4231 assert(conshdlrdata != NULL);
4232
4235
4236 /* create target constraint data */
4237 SCIP_CALL( consdataCreate(scip, &targetdata, conshdlrdata->eventhdlr,
4238 sourcedata->nvars, sourcedata->vars, sourcedata->resvar, sourcedata->checkwhenupgr,
4239 sourcedata->notremovablewhenupgr) );
4240
4241 /* create target constraint */
4247
4248 return SCIP_OKAY;
4249}
4250
4251
4252/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4253static
4255{ /*lint --e{715}*/
4256 int i;
4257
4258 *infeasible = FALSE;
4259
4260 for( i = 0; i < nconss && !(*infeasible); i++ )
4261 {
4262 assert(SCIPconsIsInitial(conss[i]));
4263 SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4264 }
4265
4266 return SCIP_OKAY;
4267}
4268
4269
4270/** separation method of constraint handler for LP solutions */
4271static
4273{ /*lint --e{715}*/
4274 SCIP_Bool separated;
4275 SCIP_Bool cutoff;
4276 int c;
4277
4279
4280 /* separate all useful constraints */
4281 for( c = 0; c < nusefulconss; ++c )
4282 {
4283 SCIP_CALL( separateCons(scip, conss[c], NULL, &separated, &cutoff) );
4284 if ( cutoff )
4286 else if ( separated )
4288 }
4289
4290 /* combine constraints to get more cuts */
4291 /**@todo combine constraints to get further cuts */
4292
4293 return SCIP_OKAY;
4294}
4295
4296
4297/** separation method of constraint handler for arbitrary primal solutions */
4298static
4300{ /*lint --e{715}*/
4301 SCIP_Bool separated;
4302 SCIP_Bool cutoff;
4303 int c;
4304
4306
4307 /* separate all useful constraints */
4308 for( c = 0; c < nusefulconss; ++c )
4309 {
4310 SCIP_CALL( separateCons(scip, conss[c], sol, &separated, &cutoff) );
4311 if ( cutoff )
4313 else if ( separated )
4315 }
4316
4317 /* combine constraints to get more cuts */
4318 /**@todo combine constraints to get further cuts */
4319
4320 return SCIP_OKAY;
4321}
4322
4323
4324/** constraint enforcing method of constraint handler for LP solutions */
4325static
4327{ /*lint --e{715}*/
4328 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
4329
4330 return SCIP_OKAY;
4331}
4332
4333/** constraint enforcing method of constraint handler for relaxation solutions */
4334static
4336{ /*lint --e{715}*/
4337 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
4338
4339 return SCIP_OKAY;
4340}
4341
4342/** constraint enforcing method of constraint handler for pseudo solutions */
4343static
4345{ /*lint --e{715}*/
4346 SCIP_Bool violated;
4347 int i;
4348
4349 /* method is called only for integral solutions, because the enforcing priority is negative */
4350 for( i = 0; i < nconss; i++ )
4351 {
4352 SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
4353 if( violated )
4354 {
4356 return SCIP_OKAY;
4357 }
4358 }
4360
4361 return SCIP_OKAY;
4362}
4363
4364
4365/** feasibility check method of constraint handler for integral solutions */
4366static
4368{ /*lint --e{715}*/
4369 SCIP_Bool violated;
4370 int i;
4371
4373
4374 /* method is called only for integral solutions, because the enforcing priority is negative */
4375 for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
4376 {
4377 SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, printreason, &violated) );
4378 if( violated )
4380 }
4381
4382 return SCIP_OKAY;
4383}
4384
4385
4386/** domain propagation method of constraint handler */
4387static
4389{ /*lint --e{715}*/
4390 SCIP_CONSHDLRDATA* conshdlrdata;
4391 SCIP_Bool cutoff;
4392 int nfixedvars;
4393 int nupgdconss;
4394 int c;
4395
4396 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4397 assert(conshdlrdata != NULL);
4398
4399 cutoff = FALSE;
4400 nfixedvars = 0;
4401 nupgdconss = 0;
4402
4403 /* propagate all useful constraints */
4404 for( c = 0; c < nusefulconss && !cutoff; ++c )
4405 {
4406 SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nupgdconss) );
4407 }
4408
4409 /* return the correct result */
4410 if( cutoff )
4412 else if( nfixedvars > 0 || nupgdconss > 0 )
4414 else
4416
4417 return SCIP_OKAY;
4418}
4419
4420
4421/** presolving method of constraint handler */
4422static
4424{ /*lint --e{715}*/
4425 SCIP_CONSHDLRDATA* conshdlrdata;
4426 SCIP_CONS* cons;
4427 SCIP_CONSDATA* consdata;
4428 unsigned char* entries;
4429 SCIP_Bool cutoff;
4430 int oldnfixedvars;
4431 int oldnaggrvars;
4432 int oldnchgbds;
4433 int oldndelconss;
4434 int oldnupgdconss;
4435 int firstchange;
4436 int nentries;
4437 int c;
4438
4439 assert(result != NULL);
4440
4441 oldnfixedvars = *nfixedvars;
4442 oldnaggrvars = *naggrvars;
4443 oldnchgbds = *nchgbds;
4444 oldndelconss = *ndelconss;
4445 oldnupgdconss = *nupgdconss;
4446
4447 nentries = SCIPgetNVars(scip) - SCIPgetNContVars(scip);
4449
4450 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4451 assert(conshdlrdata != NULL);
4452
4453 /* process constraints */
4454 cutoff = FALSE;
4456 for( c = 0; c < nconss && !cutoff && (c % 1000 != 0 || !SCIPisStopped(scip)); ++c )
4457 {
4458 cons = conss[c];
4459 assert(cons != NULL);
4460 consdata = SCIPconsGetData(cons);
4461 assert(consdata != NULL);
4462
4463 /* force presolving the constraint in the initial round */
4464 if( nrounds == 0 )
4465 consdata->propagated = FALSE;
4466
4467 /* remember the first changed constraint to begin the next aggregation round with */
4468 if( firstchange == INT_MAX && consdata->changed )
4469 firstchange = c;
4470
4471 /* propagate constraint */
4472 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4473
4474 /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4475 * fix resultant to zero if a pair of negated variables is contained in the operand variables
4476 */
4477 if( !cutoff && !SCIPconsIsDeleted(cons) )
4478 {
4479 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4480
4481 /* merge multiple occurances of variables or variables with their negated variables */
4482 SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4483 }
4484
4485 if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
4486 {
4487 assert(consdata->nvars >= 1); /* otherwise, propagateCons() has deleted the constraint */
4488
4489 /* if only one variable is left, the resultant has to be equal to this single variable */
4490 if( consdata->nvars == 1 )
4491 {
4492 SCIP_Bool redundant;
4493 SCIP_Bool aggregated;
4494
4495 SCIPdebugMsg(scip, "AND-constraint <%s> has only one variable not fixed to 1.0\n", SCIPconsGetName(cons));
4496
4497 assert(consdata->vars != NULL);
4498 assert(SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
4499 assert(SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
4500
4501 /* aggregate variables: resultant - operand == 0 */
4502 SCIP_CALL( SCIPaggregateVars(scip, consdata->resvar, consdata->vars[0], 1.0, -1.0, 0.0,
4503 &cutoff, &redundant, &aggregated) );
4504 assert(redundant || SCIPdoNotAggr(scip));
4505
4506 if( aggregated )
4507 {
4508 assert(redundant);
4509 (*naggrvars)++;
4510 }
4511
4512 if( redundant )
4513 {
4514 /* delete constraint */
4515 SCIP_CALL( SCIPdelCons(scip, cons) );
4516 (*ndelconss)++;
4517 }
4518 }
4519 else if( !consdata->impladded )
4520 {
4521 int i;
4522
4523 /* add implications: resultant == 1 -> all operands == 1 */
4524 for( i = 0; i < consdata->nvars && !cutoff; ++i )
4525 {
4526 int nimplbdchgs;
4527
4528 SCIP_CALL( SCIPaddVarImplication(scip, consdata->resvar, TRUE, consdata->vars[i],
4530 (*nchgbds) += nimplbdchgs;
4531 }
4532 consdata->impladded = TRUE;
4533 }
4534
4535 /* if in r = x and y, the resultant is fixed to zero, add implication x = 1 -> y = 0 */
4536 if( !cutoff && SCIPconsIsActive(cons) && consdata->nvars == 2 && !consdata->opimpladded
4537 && SCIPvarGetUbGlobal(consdata->resvar) < 0.5 )
4538 {
4539 int nimplbdchgs;
4540
4541 SCIP_CALL( SCIPaddVarImplication(scip, consdata->vars[0], TRUE, consdata->vars[1],
4543 (*nchgbds) += nimplbdchgs;
4544 consdata->opimpladded = TRUE;
4545 }
4546 }
4547 }
4548
4549 /* perform dual presolving on AND-constraints */
4550 if( conshdlrdata->dualpresolving && !cutoff && !SCIPisStopped(scip) && SCIPallowStrongDualReds(scip))
4551 {
4552 SCIP_CALL( dualPresolve(scip, conss, nconss, conshdlrdata->eventhdlr, &entries, &nentries, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, nupgdconss, naddconss) );
4553 }
4554
4555 /* check for cliques inside the AND constraint */
4556 if( (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4557 {
4558 for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4559 {
4560 cons = conss[c];
4561 assert(cons != NULL);
4562
4563 if( !SCIPconsIsActive(cons) )
4564 continue;
4565
4566 /* cliquePresolve() may aggregate variables which need to be removed from other constraints, we also need
4567 * to make sure that we remove fixed variables by calling propagateCons() to make sure that applyFixing()
4568 * and mergeMultiples() work
4569 */
4570 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nupgdconss) );
4571
4572 if( !cutoff && !SCIPconsIsDeleted(cons) )
4573 {
4574 /* remove all variables that are fixed to one; merge multiple entries of the same variable;
4575 * fix resultant to zero if a pair of negated variables is contained in the operand variables
4576 */
4577 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs) );
4578 SCIP_CALL( mergeMultiples(scip, cons, conshdlrdata->eventhdlr, &entries, &nentries, nfixedvars, nchgcoefs, ndelconss) );
4579
4580 /* check if at least two operands are in one clique */
4581 SCIP_CALL( cliquePresolve(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, naggrvars, nchgcoefs, ndelconss, naddconss) );
4582 }
4583 }
4584 }
4585
4586 /* process pairs of constraints: check them for equal operands in order to aggregate resultants;
4587 * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
4588 * (otherwise, we delay the presolving to be called again next time)
4589 */
4590 if( !cutoff && conshdlrdata->presolusehashing && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4591 {
4592 if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4593 {
4594 if( firstchange < nconss )
4595 {
4596 /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
4597 SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, &cutoff, naggrvars, ndelconss) );
4598 oldnaggrvars = *naggrvars;
4599 }
4600 }
4601 }
4602
4603 if( !cutoff && conshdlrdata->presolpairwise && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 )
4604 {
4605 if( *nfixedvars == oldnfixedvars && *naggrvars == oldnaggrvars )
4606 {
4607 SCIP_Longint npaircomparisons;
4608 npaircomparisons = 0;
4609 oldndelconss = *ndelconss;
4610
4611 for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
4612 {
4613 if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
4614 {
4615 npaircomparisons += ((SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange));
4616
4617 SCIP_CALL( preprocessConstraintPairs(scip, conss, firstchange, c, &cutoff, naggrvars, nchgbds,
4618 ndelconss) );
4619
4621 {
4622 if( ((*ndelconss - oldndelconss) + (*naggrvars - oldnaggrvars) + (*nchgbds - oldnchgbds)/2.0) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
4623 break;
4624 oldndelconss = *ndelconss;
4625 oldnaggrvars = *naggrvars;
4626 oldnchgbds = *nchgbds;
4627
4628 npaircomparisons = 0;
4629 }
4630 }
4631 }
4632 }
4633 }
4634
4636
4637 /* return the correct result code */
4638 if( cutoff )
4640 else if( *nfixedvars > oldnfixedvars || *naggrvars > oldnaggrvars || *nchgbds > oldnchgbds
4641 || *ndelconss > oldndelconss || *nupgdconss > oldnupgdconss )
4643 else
4645
4646 return SCIP_OKAY;
4647}
4648
4649
4650/** propagation conflict resolving method of constraint handler */
4651static
4653{ /*lint --e{715}*/
4654 SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
4655
4656 return SCIP_OKAY;
4657}
4658
4659
4660/** variable rounding lock method of constraint handler */
4661static
4663{ /*lint --e{715}*/
4664 SCIP_CONSDATA* consdata;
4665 int i;
4666
4668
4669 consdata = SCIPconsGetData(cons);
4670 assert(consdata != NULL);
4671
4672 /* resultant variable */
4673 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->resvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4674
4675 /* operand variables */
4676 for( i = 0; i < consdata->nvars; ++i )
4677 {
4678 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
4679 }
4680
4681 return SCIP_OKAY;
4682}
4683
4684/** constraint activation notification method of constraint handler */
4685static
4687{ /*lint --e{715}*/
4689 {
4690 SCIP_CALL( addNlrow(scip, cons) );
4691 }
4692
4693 return SCIP_OKAY;
4694}
4695
4696/** constraint deactivation notification method of constraint handler */
4697static
4699{ /*lint --e{715}*/
4700 SCIP_CONSDATA* consdata;
4701
4702 assert(cons != NULL);
4703
4704 consdata = SCIPconsGetData(cons);
4705 assert(consdata != NULL);
4706
4707 /* remove row from NLP, if still in solving
4708 * if we are in exitsolve, the whole NLP will be freed anyway
4709 */
4710 if( SCIPgetStage(scip) == SCIP_STAGE_SOLVING && consdata->nlrow != NULL )
4711 {
4712 SCIP_CALL( SCIPdelNlRow(scip, consdata->nlrow) );
4713 }
4714
4715 return SCIP_OKAY;
4716}
4717
4718/** constraint display method of constraint handler */
4719static
4721{ /*lint --e{715}*/
4722 assert( scip != NULL );
4723 assert( conshdlr != NULL );
4724 assert( cons != NULL );
4725
4727
4728 return SCIP_OKAY;
4729}
4730
4731/** constraint copying method of constraint handler */
4732static
4734{ /*lint --e{715}*/
4736 SCIP_VAR** vars;
4738 SCIP_VAR* resvar;
4739 const char* consname;
4740 int nvars;
4741 int v;
4742
4743 assert(valid != NULL);
4744 (*valid) = TRUE;
4745
4747
4748 /* map resultant to active variable of the target SCIP */
4749 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourceresvar, &resvar, varmap, consmap, global, valid) );
4750 assert(!(*valid) || resvar != NULL);
4751
4752 /* we do not copy, if a variable is missing */
4753 if( !(*valid) )
4754 return SCIP_OKAY;
4755
4756 /* map operand variables to active variables of the target SCIP */
4757 sourcevars = SCIPgetVarsAnd(sourcescip, sourcecons);
4758 nvars = SCIPgetNVarsAnd(sourcescip, sourcecons);
4759
4760 if( nvars == -1 )
4761 return SCIP_INVALIDCALL;
4762
4763 /* allocate buffer array */
4765
4766 for( v = 0; v < nvars; ++v )
4767 {
4768 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &vars[v], varmap, consmap, global, valid) );
4769 assert(!(*valid) || vars[v] != NULL);
4770
4771 /* we do not copy, if a variable is missing */
4772 if( !(*valid) )
4773 goto TERMINATE;
4774 }
4775
4776 if( name != NULL )
4777 consname = name;
4778 else
4779 consname = SCIPconsGetName(sourcecons);
4780
4781 /* creates and captures a AND-constraint */
4782 SCIP_CALL( SCIPcreateConsAnd(scip, cons, consname, resvar, nvars, vars,
4783 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4784
4785 TERMINATE:
4786 /* free buffer array */
4788
4789 return SCIP_OKAY;
4790}
4791
4792/** constraint parsing method of constraint handler */
4793static
4795{ /*lint --e{715}*/
4796 SCIP_VAR** vars;
4797 SCIP_VAR* resvar;
4798 char* endptr;
4799 int requiredsize;
4800 int varssize;
4801 int nvars;
4802
4803 SCIPdebugMsg(scip, "parse <%s> as AND-constraint\n", str);
4804
4805 *success = FALSE;
4806
4807 /* parse variable name of resultant */
4808 SCIP_CALL( SCIPparseVarName(scip, str, &resvar, &endptr) );
4809
4810 if( resvar == NULL )
4811 {
4812 SCIPerrorMessage("resultant variable does not exist\n");
4813 }
4814 else
4815 {
4816 char* strcopy = NULL;
4817 char* startptr;
4818
4819 str = endptr;
4820
4821 /* cutoff "== and(" form the constraint string */
4822 startptr = strchr((char*)str, '(');
4823
4824 if( startptr == NULL )
4825 {
4826 SCIPerrorMessage("missing starting character '(' parsing AND-constraint\n");
4827 return SCIP_OKAY;
4828 }
4829
4830 /* skip '(' */
4831 ++startptr;
4832
4833 /* find end character ')' */
4834 endptr = strrchr(startptr, ')');
4835
4836 if( endptr == NULL )
4837 {
4838 SCIPerrorMessage("missing ending character ')' parsing AND-constraint\n");
4839 return SCIP_OKAY;
4840 }
4842
4843 if( endptr > startptr )
4844 {
4845 /* copy string for parsing; note that SCIPskipSpace() in SCIPparseVarsList() requires that strcopy ends with '\0' */
4847 strcopy[endptr-startptr] = '\0';
4848 varssize = 100;
4849 nvars = 0;
4850
4851 /* allocate buffer array for variables */
4852 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
4853
4854 /* parse string */
4856
4857 if( *success )
4858 {
4859 /* check if the size of the variable array was great enough */
4860 if( varssize < requiredsize )
4861 {
4862 /* reallocate memory */
4863 varssize = requiredsize;
4864 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
4865
4866 /* parse string again with the correct size of the variable array */
4868 }
4869
4870 assert(*success);
4871 assert(varssize >= requiredsize);
4872
4873 /* create AND-constraint */
4874 SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
4875 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4876 }
4877
4878 /* free variable buffer */
4881 }
4882 else
4883 {
4884 if( !modifiable )
4885 {
4886 SCIPerrorMessage("cannot create empty AND-constraint\n");
4887 return SCIP_OKAY;
4888 }
4889
4890 /* create empty AND-constraint */
4891 SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, 0, NULL,
4892 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
4893
4894 *success = TRUE;
4895 }
4896 }
4897
4898 return SCIP_OKAY;
4899}
4900
4901/** constraint method of constraint handler which returns the variables (if possible) */
4902static
4904{ /*lint --e{715}*/
4905 SCIP_CONSDATA* consdata;
4906
4907 consdata = SCIPconsGetData(cons);
4908 assert(consdata != NULL);
4909
4911 (*success) = FALSE;
4912 else
4913 {
4914 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
4915 vars[consdata->nvars] = consdata->resvar;
4916 (*success) = TRUE;
4917 }
4918
4919 return SCIP_OKAY;
4920}
4921
4922/** constraint method of constraint handler which returns the number of variable (if possible) */
4923static
4925{ /*lint --e{715}*/
4926 SCIP_CONSDATA* consdata;
4927
4928 assert(cons != NULL);
4929
4930 consdata = SCIPconsGetData(cons);
4931 assert(consdata != NULL);
4932
4933 (*nvars) = consdata->nvars + 1;
4934 (*success) = TRUE;
4935
4936 return SCIP_OKAY;
4937}
4938
4939/** constraint handler method which returns the permutation symmetry detection graph of a constraint */
4940static
4942{ /*lint --e{715}*/
4944
4945 return SCIP_OKAY;
4946}
4947
4948/** constraint handler method which returns the signed permutation symmetry detection graph of a constraint */
4949static
4956
4957/*
4958 * Callback methods of event handler
4959 */
4960
4961static
4963{ /*lint --e{715}*/
4964 SCIP_CONSDATA* consdata;
4965
4966 assert(eventhdlr != NULL);
4967 assert(eventdata != NULL);
4968 assert(event != NULL);
4969
4970 consdata = (SCIP_CONSDATA*)eventdata;
4971 assert(consdata != NULL);
4972
4973 /* check, if the variable was fixed to zero */
4975 consdata->nofixedzero = FALSE;
4976
4977 consdata->propagated = FALSE;
4978
4979 return SCIP_OKAY;
4980}
4981
4982
4983/*
4984 * constraint specific interface methods
4985 */
4986
4987/** creates the handler for AND-constraints and includes it in SCIP */
4989 SCIP* scip /**< SCIP data structure */
4990 )
4991{
4992 SCIP_CONSHDLRDATA* conshdlrdata;
4993 SCIP_CONSHDLR* conshdlr;
4994 SCIP_EVENTHDLR* eventhdlr;
4995
4996 /* create event handler for events on variables */
4998 eventExecAnd, NULL) );
4999
5000 /* create constraint handler data */
5001 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5002
5003 /* include constraint handler */
5007 conshdlrdata) );
5008
5009 assert(conshdlr != NULL);
5010
5011 /* set non-fundamental callbacks via specific setter functions */
5016#ifdef GMLGATEPRINTING
5018#endif
5038
5039 /* add AND-constraint handler parameters */
5041 "constraints/" CONSHDLR_NAME "/presolpairwise",
5042 "should pairwise constraint comparison be performed in presolving?",
5043 &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5045 "constraints/and/presolusehashing",
5046 "should hash table be used for detecting redundant constraints in advance",
5047 &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
5049 "constraints/" CONSHDLR_NAME "/linearize",
5050 "should the AND-constraint get linearized and removed (in presolving)?",
5051 &conshdlrdata->linearize, TRUE, DEFAULT_LINEARIZE, NULL, NULL) );
5053 "constraints/" CONSHDLR_NAME "/enforcecuts",
5054 "should cuts be separated during LP enforcing?",
5055 &conshdlrdata->enforcecuts, TRUE, DEFAULT_ENFORCECUTS, NULL, NULL) );
5057 "constraints/" CONSHDLR_NAME "/aggrlinearization",
5058 "should an aggregated linearization be used?",
5059 &conshdlrdata->aggrlinearization, TRUE, DEFAULT_AGGRLINEARIZATION, NULL, NULL) );
5061 "constraints/" CONSHDLR_NAME "/upgraderesultant",
5062 "should all binary resultant variables be upgraded to implicit binary variables?",
5063 &conshdlrdata->upgrresultant, TRUE, DEFAULT_UPGRRESULTANT, NULL, NULL) );
5065 "constraints/" CONSHDLR_NAME "/dualpresolving",
5066 "should dual presolving be performed?",
5067 &conshdlrdata->dualpresolving, TRUE, DEFAULT_DUALPRESOLVING, NULL, NULL) );
5068
5069 return SCIP_OKAY;
5070}
5071
5072/** creates and captures a AND-constraint
5073 *
5074 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5075 */
5077 SCIP* scip, /**< SCIP data structure */
5078 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5079 const char* name, /**< name of constraint */
5080 SCIP_VAR* resvar, /**< resultant variable of the operation */
5081 int nvars, /**< number of operator variables in the constraint */
5082 SCIP_VAR** vars, /**< array with operator variables of constraint */
5083 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5084 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5085 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5086 * Usually set to TRUE. */
5087 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5088 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5089 SCIP_Bool check, /**< should the constraint be checked for feasibility?
5090 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5091 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5092 * Usually set to TRUE. */
5093 SCIP_Bool local, /**< is constraint only valid locally?
5094 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5095 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5096 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5097 * adds coefficients to this constraint. */
5098 SCIP_Bool dynamic, /**< is constraint subject to aging?
5099 * Usually set to FALSE. Set to TRUE for own cuts which
5100 * are separated as constraints. */
5101 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5102 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5103 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5104 * if it may be moved to a more global node?
5105 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5106 )
5107{
5108 SCIP_CONSHDLR* conshdlr;
5109 SCIP_CONSHDLRDATA* conshdlrdata;
5110 SCIP_CONSDATA* consdata;
5111 SCIP_Bool infeasible;
5112
5113 /* find the AND-constraint handler */
5114 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5115 if( conshdlr == NULL )
5116 {
5117 SCIPerrorMessage("AND-constraint handler not found\n");
5118 return SCIP_PLUGINNOTFOUND;
5119 }
5120
5121 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5122 assert(conshdlrdata != NULL);
5123
5124 /* upgrade binary resultant variable to an implicit binary variable */
5125 /* @todo add implicit upgrade in presolving, improve decision making for upgrade by creating an implication graph */
5126 if( conshdlrdata->upgrresultant && SCIPvarGetType(resvar) == SCIP_VARTYPE_BINARY
5127#if 1 /* todo delete following hack,
5128 * the following avoids upgrading not artificial variables, for example and-resultants which are generated
5129 * from the gate presolver, it seems better to not upgrade these variables
5130 */
5132#else
5133 )
5134#endif
5135 {
5138 int v;
5139
5140 if( SCIPisTransformed(scip) )
5142 else
5143 activeresvar = resvar;
5144
5146 {
5147 /* check if we can upgrade the variable type of the resultant */
5148 for( v = nvars - 1; v >= 0; --v )
5149 {
5150 if( SCIPisTransformed(scip) )
5152 else
5153 activevar = vars[v];
5154
5156 break;
5157 }
5158
5159 /* upgrade the type of the resultant */
5160 if( v < 0 )
5161 {
5162 SCIP_CALL( SCIPchgVarType(scip, resvar, SCIP_VARTYPE_IMPLINT, &infeasible) );
5163 assert(!infeasible);
5164 }
5165 }
5166 }
5167
5168 /* create constraint data */
5169 SCIP_CALL( consdataCreate(scip, &consdata, conshdlrdata->eventhdlr, nvars, vars, resvar, FALSE, FALSE) );
5170
5171 /* create constraint */
5172 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5173 local, modifiable, dynamic, removable, stickingatnode) );
5174
5175 return SCIP_OKAY;
5176}
5177
5178/** creates and captures an AND-constraint
5179 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
5180 * method SCIPcreateConsAnd(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
5181 *
5182 * @see SCIPcreateConsAnd() for information about the basic constraint flag configuration
5183 *
5184 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5185 */
5187 SCIP* scip, /**< SCIP data structure */
5188 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5189 const char* name, /**< name of constraint */
5190 SCIP_VAR* resvar, /**< resultant variable of the operation */
5191 int nvars, /**< number of operator variables in the constraint */
5192 SCIP_VAR** vars /**< array with operator variables of constraint */
5193 )
5194{
5195 assert(scip != NULL);
5196
5197 SCIP_CALL( SCIPcreateConsAnd(scip, cons, name, resvar, nvars, vars,
5199
5200 return SCIP_OKAY;
5201}
5202
5203
5204/** gets number of variables in AND-constraint */
5206 SCIP* scip, /**< SCIP data structure */
5207 SCIP_CONS* cons /**< constraint data */
5208 )
5209{
5210 SCIP_CONSDATA* consdata;
5211
5212 assert(scip != NULL);
5213 assert(cons != NULL);
5214
5216 {
5217 SCIPerrorMessage("constraint is not an AND-constraint\n");
5218 SCIPABORT();
5219 return -1; /*lint !e527*/
5220 }
5221
5222 consdata = SCIPconsGetData(cons);
5223 assert(consdata != NULL);
5224
5225 return consdata->nvars;
5226}
5227
5228/** gets array of variables in AND-constraint */
5230 SCIP* scip, /**< SCIP data structure */
5231 SCIP_CONS* cons /**< constraint data */
5232 )
5233{ /*lint --e{715}*/
5234 SCIP_CONSDATA* consdata;
5235
5236 assert(scip != NULL);
5237 assert(cons != NULL);
5238
5240 {
5241 SCIPerrorMessage("constraint is not an AND-constraint\n");
5242 SCIPABORT();
5243 return NULL; /*lint !e527*/
5244 }
5245
5246 consdata = SCIPconsGetData(cons);
5247 assert(consdata != NULL);
5248
5249 return consdata->vars;
5250}
5251
5252
5253/** gets the resultant variable in AND-constraint */ /*lint -e715*/
5255 SCIP* scip, /**< SCIP data structure */
5256 SCIP_CONS* cons /**< constraint data */
5257 )
5258{
5259 SCIP_CONSDATA* consdata;
5260
5261 assert(cons != NULL);
5262
5264 {
5265 SCIPerrorMessage("constraint is not an AND-constraint\n");
5266 SCIPABORT();
5267 return NULL; /*lint !e527*/
5268 }
5269
5270 consdata = SCIPconsGetData(cons);
5271 assert(consdata != NULL);
5272
5273 return consdata->resvar;
5274}
5275
5276/** return if the variables of the AND-constraint are sorted with respect to their indices */
5278 SCIP* scip, /**< SCIP data structure */
5279 SCIP_CONS* cons /**< constraint data */
5280 )
5281{
5282 SCIP_CONSDATA* consdata;
5283
5284 assert(scip != NULL);
5285 assert(cons != NULL);
5286
5288 {
5289 SCIPerrorMessage("constraint is not an AND-constraint\n");
5290 SCIPABORT();
5291 return FALSE; /*lint !e527*/
5292 }
5293
5294 consdata = SCIPconsGetData(cons);
5295 assert(consdata != NULL);
5296
5297 return consdata->sorted;
5298}
5299
5300/** sort the variables of the AND-constraint with respect to their indices */
5302 SCIP* scip, /**< SCIP data structure */
5303 SCIP_CONS* cons /**< constraint data */
5304 )
5305{
5306 SCIP_CONSDATA* consdata;
5307
5308 assert(scip != NULL);
5309 assert(cons != NULL);
5310
5312 {
5313 SCIPerrorMessage("constraint is not an AND-constraint\n");
5314 SCIPABORT();
5315 return SCIP_INVALIDDATA; /*lint !e527*/
5316 }
5317
5318 consdata = SCIPconsGetData(cons);
5319 assert(consdata != NULL);
5320
5321 consdataSort(consdata);
5322 assert(consdata->sorted);
5323
5324 return SCIP_OKAY;
5325}
5326
5327/** when 'upgrading' the given AND-constraint, should the check flag for the upgraded constraint be set to TRUE, even if
5328 * the check flag of this AND-constraint is set to FALSE?
5329 */
5331 SCIP* scip, /**< SCIP data structure */
5332 SCIP_CONS* cons, /**< constraint data */
5333 SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be checked,
5334 * even if the check flag of the AND-constraint is set to FALSE
5335 */
5336 )
5337{
5338 SCIP_CONSDATA* consdata;
5339
5340 assert(scip != NULL);
5341 assert(cons != NULL);
5342
5344 {
5345 SCIPerrorMessage("constraint is not an AND-constraint\n");
5346 SCIPABORT();
5347 return SCIP_INVALIDDATA; /*lint !e527*/
5348 }
5349
5350 consdata = SCIPconsGetData(cons);
5351 assert(consdata != NULL);
5352
5353 consdata->checkwhenupgr = flag;
5354
5355 return SCIP_OKAY;
5356}
5357
5358/** when 'upgrading' the given AND-constraint, should the removable flag for the upgraded constraint be set to FALSE,
5359 * even if the removable flag of this AND-constraint is set to TRUE?
5360 */
5362 SCIP* scip, /**< SCIP data structure */
5363 SCIP_CONS* cons, /**< constraint data */
5364 SCIP_Bool flag /**< should an arising constraint from the given AND-constraint be not
5365 * removable, even if the removable flag of the AND-constraint is set to
5366 * TRUE
5367 */
5368 )
5369{
5370 SCIP_CONSDATA* consdata;
5371
5372 assert(scip != NULL);
5373 assert(cons != NULL);
5374
5376 {
5377 SCIPerrorMessage("constraint is not an AND-constraint\n");
5378 SCIPABORT();
5379 return SCIP_INVALIDDATA; /*lint !e527*/
5380 }
5381
5382 consdata = SCIPconsGetData(cons);
5383 assert(consdata != NULL);
5384
5385 consdata->notremovablewhenupgr = flag;
5386
5387 return SCIP_OKAY;
5388}
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_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:2030
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_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
#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:1356
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition cons_and.c:1200
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_VAR *var)
Definition cons_and.c:621
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_RETCODE analyzeZeroResultant(SCIP *scip, SCIP_CONS *cons, int watchedvar1, int watchedvar2, SCIP_Bool *cutoff, int *nfixedvars)
Definition cons_and.c:1521
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_RETCODE consdataFixResultantZero(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *resvar, int pos, SCIP_Bool *cutoff, int *nfixedvars)
Definition cons_and.c:1317
#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:1249
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:3408
#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:2682
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:3585
static SCIP_RETCODE consdataLinearize(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *cutoff, int *nfixedvars, int *nupgdconss)
Definition cons_and.c:1410
static SCIP_RETCODE addSymmetryInformation(SCIP *scip, SYM_SYMTYPE symtype, SCIP_CONS *cons, SYM_GRAPH *graph, SCIP_Bool *success)
Definition cons_and.c:3789
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_and.c:188
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_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:1281
#define CONSHDLR_PROPFREQ
Definition cons_and.c:91
#define NMINCOMPARISONS
Definition cons_and.c:114
#define DEFAULT_ENFORCECUTS
Definition cons_and.c:107
#define CONSHDLR_PRESOLTIMING
Definition cons_and.c:99
static void consdataSort(SCIP_CONSDATA *consdata)
Definition cons_and.c:744
static SCIP_RETCODE addNlrow(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:1032
#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
#define CONSHDLR_ENFOPRIORITY
Definition cons_and.c:88
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:1944
#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:1582
static SCIP_RETCODE enforceConstraint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, SCIP_SOL *sol, SCIP_RESULT *result)
Definition cons_and.c:3528
#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:1739
#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
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 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:5076
SCIP_RETCODE SCIPchgAndConsCheckFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition cons_and.c:5330
SCIP_VAR * SCIPgetResultantAnd(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5254
int SCIPgetNVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5205
SCIP_RETCODE SCIPchgAndConsRemovableFlagWhenUpgr(SCIP *scip, SCIP_CONS *cons, SCIP_Bool flag)
Definition cons_and.c:5361
SCIP_RETCODE SCIPcreateConsSetpack(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_RETCODE SCIPsortAndCons(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5301
SCIP_Bool SCIPisAndConsSorted(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5277
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)
SCIP_VAR ** SCIPgetVarsAnd(SCIP *scip, SCIP_CONS *cons)
Definition cons_and.c:5229
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:5186
SCIP_RETCODE SCIPincludeConshdlrAnd(SCIP *scip)
Definition cons_and.c:4988
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)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
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,...)
#define SCIPdebugMsgPrint
#define SCIPdebugMsg
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)
void SCIPconshdlrSetData(SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
Definition cons.c:4227
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrActive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:670
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrInitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
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 SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:323
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 SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:808
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:831
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:785
SCIP_RETCODE SCIPsetConshdlrGetSignedPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:924
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
Definition scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrGetPermsymGraph(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:900
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:444
SCIP_RETCODE SCIPsetConshdlrDeactive(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:693
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:647
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:516
SCIP_RETCODE SCIPsetConshdlrExitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:468
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:624
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:854
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)
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:4353
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:1482
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:8567
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:1646
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:8403
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:4261
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:4439
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:2130
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:1250
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
Definition scip_var.c:8178
SCIP_RETCODE SCIPgetNegatedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **negvar)
Definition scip_var.c:1529
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:6782
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:8717
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:8278
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:1994
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:5725
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:1599
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:1441
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1216
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:8631
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
return SCIP_OKAY
int c
SCIP_Bool cutoff
static SCIP_SOL * sol
int r
SCIP_Real obj
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_Bool propagate
static SCIP_VAR ** vars
int nbinvars
int nintvars
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)
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
#define SCIP_DECL_CONSGETSIGNEDPERMSYMGRAPH(x)
Definition type_cons.h:955
#define SCIP_DECL_CONSGETPERMSYMGRAPH(x)
Definition type_cons.h:937
#define SCIP_DECL_CONSENFOLP(x)
Definition type_cons.h:363
#define SCIP_DECL_CONSINITPRE(x)
Definition type_cons.h:156
#define SCIP_DECL_CONSDELETE(x)
Definition type_cons.h:229
#define SCIP_DECL_CONSGETVARS(x)
Definition type_cons.h:866
#define SCIP_DECL_CONSINITSOL(x)
Definition type_cons.h:201
#define SCIP_DECL_CONSPRINT(x)
Definition type_cons.h:768
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition type_cons.h:64
#define SCIP_DECL_CONSSEPALP(x)
Definition type_cons.h:288
#define SCIP_DECL_CONSENFORELAX(x)
Definition type_cons.h:388
#define SCIP_DECL_CONSPROP(x)
Definition type_cons.h:505
#define SCIP_DECL_CONSGETNVARS(x)
Definition type_cons.h:884
#define SCIP_DECL_CONSRESPROP(x)
Definition type_cons.h:611
#define SCIP_DECL_CONSACTIVE(x)
Definition type_cons.h:690
#define SCIP_DECL_CONSENFOPS(x)
Definition type_cons.h:431
#define SCIP_DECL_CONSPARSE(x)
Definition type_cons.h:844
#define SCIP_DECL_CONSTRANS(x)
Definition type_cons.h:239
#define SCIP_DECL_CONSDEACTIVE(x)
Definition type_cons.h:705
#define SCIP_DECL_CONSPRESOL(x)
Definition type_cons.h:560
#define SCIP_DECL_CONSINITLP(x)
Definition type_cons.h:259
#define SCIP_DECL_CONSEXITPRE(x)
Definition type_cons.h:180
#define SCIP_DECL_CONSLOCK(x)
Definition type_cons.h:675
#define SCIP_DECL_CONSCOPY(x)
Definition type_cons.h:809
struct SCIP_ConsData SCIP_CONSDATA
Definition type_cons.h:65
#define SCIP_DECL_CONSCHECK(x)
Definition type_cons.h:474
#define SCIP_DECL_CONSHDLRCOPY(x)
Definition type_cons.h:108
#define SCIP_DECL_CONSEXITSOL(x)
Definition type_cons.h:216
#define SCIP_DECL_CONSFREE(x)
Definition type_cons.h:116
#define SCIP_DECL_CONSSEPASOL(x)
Definition type_cons.h:320
#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_DECL_EVENTEXEC(x)
Definition type_event.h:253
#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
#define SCIP_DECL_HASHKEYEQ(x)
Definition type_misc.h:194
#define SCIP_DECL_HASHGETKEY(x)
Definition type_misc.h:191
#define SCIP_DECL_HASHKEYVAL(x)
Definition type_misc.h:197
@ 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
@ SCIP_PLUGINNOTFOUND
@ SCIP_WRITEERROR
@ SCIP_INVALIDCALL
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_STAGE_EXITPRESOLVE
Definition type_set.h:50
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
enum SYM_Symtype SYM_SYMTYPE
@ SYM_SYMTYPE_SIGNPERM
@ SYM_SYMTYPE_PERM
#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