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