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