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