Scippy

SCIP

Solving Constraint Integer Programs

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