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