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