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