SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
cons_xor.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_xor.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief Constraint handler for "xor" constraints, \f$rhs = x_1 \oplus x_2 \oplus \dots \oplus x_n\f$
28 * @author Tobias Achterberg
29 * @author Stefan Heinz
30 * @author Marc Pfetsch
31 * @author Michael Winkler
32 *
33 * This constraint handler deals with "xor" constraint. These are constraint of the form:
34 *
35 * \f[
36 * rhs = x_1 \oplus x_2 \oplus \dots \oplus x_n
37 * \f]
38 *
39 * where \f$x_i\f$ is a binary variable for all \f$i\f$ and \f$rhs\f$ is bool. The variables \f$x\f$'s are called
40 * operators. This constraint is satisfied if \f$rhs\f$ is TRUE and an odd number of the operators are TRUE or if the
41 * \f$rhs\f$ is FALSE and a even number of operators are TRUE. Hence, if the sum of \f$rhs\f$ and operators is even.
42 *
43 * @todo reduce code duplication
44 * - unified treatment of constraint with 0/1/2 binary variables
45 * - static functions for certain operations that respect deleteintvar flag properly (e.g., deletion of constraints)
46 * @todo add offset for activity which might allow to handle intvar in a more unified way
47 * (right now, we do not remove fixed variables from the constraint, because we must ensure that the intvar gets
48 * the correct value in the end)
49 * @todo check if preprocessConstraintPairs can also be executed for non-artificial intvars (after the previous changes)
50 */
51
52/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
53
55#include "scip/cons_linear.h"
56#include "scip/cons_setppc.h"
57#include "scip/cons_xor.h"
58#include "scip/debug.h"
59#include "scip/heur_trysol.h"
60#include "scip/pub_cons.h"
61#include "scip/pub_event.h"
62#include "scip/pub_lp.h"
63#include "scip/pub_message.h"
64#include "scip/pub_misc.h"
65#include "scip/pub_misc_sort.h"
66#include "scip/pub_var.h"
67#include "scip/scip_conflict.h"
68#include "scip/scip_cons.h"
69#include "scip/scip_copy.h"
70#include "scip/scip_cut.h"
71#include "scip/scip_event.h"
72#include "scip/scip_general.h"
73#include "scip/scip_heur.h"
74#include "scip/scip_lp.h"
75#include "scip/scip_mem.h"
76#include "scip/scip_message.h"
77#include "scip/scip_numerics.h"
78#include "scip/scip_param.h"
79#include "scip/scip_prob.h"
80#include "scip/scip_probing.h"
81#include "scip/scip_sol.h"
82#include "scip/scip_tree.h"
83#include "scip/scip_var.h"
84
85
86/* constraint handler properties */
87#define CONSHDLR_NAME "xor"
88#define CONSHDLR_DESC "constraint handler for xor constraints: r = xor(x1, ..., xn)"
89#define CONSHDLR_SEPAPRIORITY +850200 /**< priority of the constraint handler for separation */
90#define CONSHDLR_ENFOPRIORITY -850200 /**< priority of the constraint handler for constraint enforcing */
91#define CONSHDLR_CHECKPRIORITY -850200 /**< priority of the constraint handler for checking feasibility */
92#define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
93#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
94#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
95 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
96#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
97#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
98#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
99#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
100
101#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
102#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
103
104#define EVENTHDLR_NAME "xor"
105#define EVENTHDLR_DESC "event handler for xor constraints"
106
107#define LINCONSUPGD_PRIORITY +600000 /**< priority of the constraint handler for upgrading of linear constraints */
108
109#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
110#define DEFAULT_ADDEXTENDEDFORM FALSE /**< should the extended formulation be added in presolving? */
111#define DEFAULT_ADDFLOWEXTENDED FALSE /**< should the extended flow formulation be added (nonsymmetric formulation otherwise)? */
112#define DEFAULT_SEPARATEPARITY FALSE /**< should parity inequalities be separated? */
113#define DEFAULT_GAUSSPROPFREQ 5 /**< frequency for applying the Gauss propagator */
114#define HASHSIZE_XORCONS 500 /**< minimal size of hash table in logicor constraint tables */
115#define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
116#define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
117#define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
118#define MAXXORCONSSSYSTEM 1000 /**< maximal number of active constraints for which checking the system over GF2 is performed */
119#define MAXXORVARSSYSTEM 1000 /**< maximal number of variables in xor constraints for which checking the system over GF2 is performed */
120
121#define NROWS 5
122
123
124/*
125 * Data structures
126 */
127
128/** type used for matrix entries in function checkGauss() */
129typedef unsigned short Type;
130
131/** constraint data for xor constraints */
132struct SCIP_ConsData
133{
134 SCIP_VAR** vars; /**< variables in the xor operation */
135 SCIP_VAR* intvar; /**< internal variable for LP relaxation */
136 SCIP_VAR** extvars; /**< variables in extended (flow|asymmetric) formulation (order for flow formulation: nn, ns, sn, ss) */
137 SCIP_ROW* rows[NROWS]; /**< rows for linear relaxation of xor constraint */
138 int nvars; /**< number of variables in xor operation */
139 int nextvars; /**< number of variables in extended flow formulation */
140 int varssize; /**< size of vars array */
141 int extvarssize; /**< size of extvars array */
142 int watchedvar1; /**< position of first watched operator variable */
143 int watchedvar2; /**< position of second watched operator variable */
144 int filterpos1; /**< event filter position of first watched operator variable */
145 int filterpos2; /**< event filter position of second watched operator variable */
146 SCIP_Bool rhs; /**< right hand side of the constraint */
147 unsigned int deleteintvar:1; /**< should artificial variable be deleted */
148 unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
149 unsigned int sorted:1; /**< are the constraint's variables sorted? */
150 unsigned int changed:1; /**< was constraint changed since last pair preprocessing round? */
151};
152
153/** constraint handler data */
154struct SCIP_ConshdlrData
155{
156 SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
157 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
158 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance? */
159 SCIP_Bool addextendedform; /**< should the extended formulation be added in presolving? */
160 SCIP_Bool addflowextended; /**< should the extended flow formulation be added (nonsymmetric formulation otherwise)? */
161 SCIP_Bool separateparity; /**< should parity inequalities be separated? */
162 int gausspropfreq; /**< frequency for applying the Gauss propagator */
163};
164
165
166/*
167 * Propagation rules
168 */
169
171{
172 PROPRULE_0, /**< all variables are fixed => fix integral variable */
173 PROPRULE_1, /**< all except one variable fixed => fix remaining variable */
174 PROPRULE_INTLB, /**< lower bound propagation of integral variable */
175 PROPRULE_INTUB, /**< upper bound propagation of integral variable */
176 PROPRULE_INVALID /**< propagation was applied without a specific propagation rule */
178typedef enum Proprule PROPRULE;
179
180
181/*
182 * Local methods
183 */
184
185/** installs rounding locks for the given variable in the given xor constraint */
186static
188 SCIP* scip, /**< SCIP data structure */
189 SCIP_CONS* cons, /**< xor constraint */
190 SCIP_VAR* var /**< variable of constraint entry */
191 )
192{
194
195 /* rounding in both directions may violate the constraint */
197
198 return SCIP_OKAY;
199}
200
201/** removes rounding locks for the given variable in the given xor constraint */
202static
204 SCIP* scip, /**< SCIP data structure */
205 SCIP_CONS* cons, /**< xor constraint */
206 SCIP_VAR* var /**< variable of constraint entry */
207 )
208{
210
211 /* rounding in both directions may violate the constraint */
213
214 return SCIP_OKAY;
215}
216
217/** creates constraint handler data */
218static
220 SCIP* scip, /**< SCIP data structure */
221 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
222 SCIP_EVENTHDLR* eventhdlr /**< event handler */
223 )
224{
225 assert(scip != NULL);
226 assert(conshdlrdata != NULL);
227 assert(eventhdlr != NULL);
228
229 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
230
231 /* set event handler for catching events on watched variables */
232 (*conshdlrdata)->eventhdlr = eventhdlr;
233
234 return SCIP_OKAY;
235}
236
237/** frees constraint handler data */
238static
240 SCIP* scip, /**< SCIP data structure */
241 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
242 )
243{
244 assert(conshdlrdata != NULL);
245 assert(*conshdlrdata != NULL);
246
247 SCIPfreeBlockMemory(scip, conshdlrdata);
248}
249
250/** stores the given variable numbers as watched variables, and updates the event processing */
251static
253 SCIP* scip, /**< SCIP data structure */
254 SCIP_CONSDATA* consdata, /**< xor constraint data */
255 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
256 int watchedvar1, /**< new first watched variable */
257 int watchedvar2 /**< new second watched variable */
258 )
259{
260 assert(consdata != NULL);
261 assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
262 assert(watchedvar1 != -1 || watchedvar2 == -1);
263 assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
264 assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
265
266 /* if one watched variable is equal to the old other watched variable, just switch positions */
267 if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
268 {
269 int tmp;
270
271 tmp = consdata->watchedvar1;
272 consdata->watchedvar1 = consdata->watchedvar2;
273 consdata->watchedvar2 = tmp;
274 tmp = consdata->filterpos1;
275 consdata->filterpos1 = consdata->filterpos2;
276 consdata->filterpos2 = tmp;
277 }
278 assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
279 assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
280
281 /* drop events on old watched variables */
282 if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
283 {
284 assert(consdata->filterpos1 != -1);
285 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar1], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
286 (SCIP_EVENTDATA*)consdata, consdata->filterpos1) );
287 }
288 if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
289 {
290 assert(consdata->filterpos2 != -1);
291 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar2], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
292 (SCIP_EVENTDATA*)consdata, consdata->filterpos2) );
293 }
294
295 /* catch events on new watched variables */
296 if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
297 {
298 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar1], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
299 (SCIP_EVENTDATA*)consdata, &consdata->filterpos1) );
300 }
301 if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
302 {
303 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar2], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
304 (SCIP_EVENTDATA*)consdata, &consdata->filterpos2) );
305 }
306
307 /* set the new watched variables */
308 consdata->watchedvar1 = watchedvar1;
309 consdata->watchedvar2 = watchedvar2;
310
311 return SCIP_OKAY;
312}
313
314/** ensures, that the vars array can store at least num entries */
315static
317 SCIP* scip, /**< SCIP data structure */
318 SCIP_CONSDATA* consdata, /**< linear constraint data */
319 int num /**< minimum number of entries to store */
320 )
321{
322 assert(consdata != NULL);
323 assert(consdata->nvars <= consdata->varssize);
324
325 if( num > consdata->varssize )
326 {
327 int newsize;
328
330 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
331 consdata->varssize = newsize;
332 }
333 assert(num <= consdata->varssize);
334
335 return SCIP_OKAY;
336}
337
338/** creates constraint data for xor constraint */
339static
341 SCIP* scip, /**< SCIP data structure */
342 SCIP_CONSDATA** consdata, /**< pointer to store the constraint data */
343 SCIP_Bool rhs, /**< right hand side of the constraint */
344 int nvars, /**< number of variables in the xor operation */
345 SCIP_VAR** vars, /**< variables in xor operation */
346 SCIP_VAR* intvar /**< artificial integer variable for linear relaxation */
347 )
348{
349 int r;
350
351 assert(consdata != NULL);
352 assert(nvars == 0 || vars != NULL);
353
354 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
355 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
356
357 (*consdata)->rhs = rhs;
358 (*consdata)->intvar = intvar;
359 for( r = 0; r < NROWS; ++r )
360 (*consdata)->rows[r] = NULL;
361 (*consdata)->nvars = nvars;
362 (*consdata)->varssize = nvars;
363 (*consdata)->watchedvar1 = -1;
364 (*consdata)->watchedvar2 = -1;
365 (*consdata)->filterpos1 = -1;
366 (*consdata)->filterpos2 = -1;
367 (*consdata)->deleteintvar = (intvar == NULL);
368 (*consdata)->propagated = FALSE;
369 (*consdata)->sorted = FALSE;
370 (*consdata)->changed = TRUE;
371 (*consdata)->extvars = NULL;
372 (*consdata)->nextvars = 0;
373 (*consdata)->extvarssize = 0;
374
375 /* get transformed variables, if we are in the transformed problem */
377 {
378 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
379
380 if( (*consdata)->intvar != NULL )
381 {
382 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->intvar, &((*consdata)->intvar)) );
383 }
384
386 {
387 SCIP_CONSHDLRDATA* conshdlrdata;
388 SCIP_CONSHDLR* conshdlr;
389 int v;
390
392 assert(conshdlr != NULL);
393 conshdlrdata = SCIPconshdlrGetData(conshdlr);
394 assert(conshdlrdata != NULL);
395
396 for( v = (*consdata)->nvars - 1; v >= 0; --v )
397 {
398 SCIP_CALL( SCIPcatchVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
399 (SCIP_EVENTDATA*)(*consdata), NULL) );
400 }
401 }
402 }
403
404#ifndef NDEBUG
405 /* assert that all variables are explicit binary variables
406 * xor-check cannot handle fractional values for implicit binary variables
407 */
408 for( int v = 0; v < (*consdata)->nvars; ++v )
409 {
410 assert(SCIPvarIsBinary((*consdata)->vars[v]));
411 assert(SCIPvarGetType((*consdata)->vars[v]) != SCIP_VARTYPE_IMPLINT);
412 }
413#endif
414
415 if( (*consdata)->intvar != NULL )
416 {
417 /* capture artificial variable */
418 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->intvar) );
419 }
420
421 return SCIP_OKAY;
422}
423
424/** releases LP row of constraint data */
425static
427 SCIP* scip, /**< SCIP data structure */
428 SCIP_CONSDATA* consdata /**< constraint data */
429 )
430{
431 int r;
432
433 assert(consdata != NULL);
434
435 for( r = 0; r < NROWS; ++r )
436 {
437 if( consdata->rows[r] != NULL )
438 {
439 SCIP_CALL( SCIPreleaseRow(scip, &consdata->rows[r]) );
440 }
441 }
442
443 return SCIP_OKAY;
444}
445
446/** frees constraint data for xor constraint */
447static
449 SCIP* scip, /**< SCIP data structure */
450 SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
451 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
452 )
453{
454 assert(consdata != NULL);
455 assert(*consdata != NULL);
456
458 {
459 int j;
460
461 /* drop events for watched variables */
462 SCIP_CALL( consdataSwitchWatchedvars(scip, *consdata, eventhdlr, -1, -1) );
463
464 /* release flow variables */
465 if ( (*consdata)->nextvars > 0 )
466 {
467 assert( (*consdata)->extvars != NULL );
468 for (j = 0; j < (*consdata)->extvarssize; ++j)
469 {
470 if ( (*consdata)->extvars[j] != NULL )
471 {
472 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->extvars[j])) );
473 }
474 }
475
476 SCIPfreeBlockMemoryArray(scip, &((*consdata)->extvars), (*consdata)->extvarssize);
477 (*consdata)->nextvars = 0;
478 (*consdata)->extvarssize = 0;
479 }
480 }
481 else
482 {
483 assert((*consdata)->watchedvar1 == -1);
484 assert((*consdata)->watchedvar2 == -1);
485 }
486
487 /* release LP row */
488 SCIP_CALL( consdataFreeRows(scip, *consdata) );
489
490 /* release internal variable */
491 if( (*consdata)->intvar != NULL )
492 {
493 /* if the constraint is deleted and the integral variable is present, it should be fixed */
494 assert( SCIPisEQ(scip, SCIPvarGetLbGlobal((*consdata)->intvar), SCIPvarGetLbGlobal((*consdata)->intvar)) );
495
496 /* We do not delete the integral variable, but leave the handling to SCIP, because it might happen that the
497 integral variable is stored in some basis information somewhere. */
498 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->intvar) );
499 }
500
501 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
502 SCIPfreeBlockMemory(scip, consdata);
503
504 return SCIP_OKAY;
505}
506
507/** prints xor constraint to file stream */
508static
510 SCIP* scip, /**< SCIP data structure */
511 SCIP_CONSDATA* consdata, /**< xor constraint data */
512 FILE* file, /**< output file (or NULL for standard output) */
513 SCIP_Bool endline /**< should an endline be set? */
514 )
515{
516 assert(consdata != NULL);
517
518 /* start variable list */
519 SCIPinfoMessage(scip, file, "xor(");
520
521 /* print variable list */
522 SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
523
524 /* close variable list and write right hand side */
525 SCIPinfoMessage(scip, file, ") = %u", consdata->rhs);
526
527 /* write integer variable if it exists */
528 if( consdata->intvar != NULL )
529 {
530 SCIPinfoMessage(scip, file, " (intvar = ");
531 SCIP_CALL( SCIPwriteVarName(scip, file, consdata->intvar, TRUE) );
532 SCIPinfoMessage(scip, file, ")");
533 }
534
535 if( endline )
536 SCIPinfoMessage(scip, file, "\n");
537
538 return SCIP_OKAY;
539}
540
541/** sets intvar of an xor constraint */
542static
544 SCIP* scip, /**< SCIP data structure */
545 SCIP_CONS* cons, /**< xor constraint */
546 SCIP_VAR* var /**< variable to add to the constraint */
547 )
548{
549 SCIP_CONSDATA* consdata;
550 SCIP_Bool transformed;
551
552 assert(var != NULL);
553
554 consdata = SCIPconsGetData(cons);
555 assert(consdata != NULL);
556 assert(consdata->rows[0] == NULL);
557
558 /* are we in the transformed problem? */
559 transformed = SCIPconsIsTransformed(cons);
560
561 /* always use transformed variables in transformed constraints */
562 if( transformed )
563 {
565 }
566 assert(var != NULL);
567 assert(transformed == SCIPvarIsTransformed(var));
568
569 /* remove the rounding locks for the old variable and release it */
570 if( consdata->intvar != NULL )
571 {
572 SCIP_CALL( unlockRounding(scip, cons, consdata->intvar) );
573 SCIP_CALL( SCIPreleaseVar(scip, &(consdata->intvar)) );
574 }
575
576 consdata->intvar = var;
577 consdata->changed = TRUE;
578
579 /* install the rounding locks for the new variable and capture it */
580 SCIP_CALL( lockRounding(scip, cons, consdata->intvar) );
581 SCIP_CALL( SCIPcaptureVar(scip, consdata->intvar) );
582
583 /**@todo update LP rows */
584 if( consdata->rows[0] != NULL )
585 {
586 SCIPerrorMessage("cannot change intvar of xor constraint after LP relaxation was created\n");
587 return SCIP_INVALIDCALL;
588 }
589
590 return SCIP_OKAY;
591}
592
593/** adds coefficient to xor constraint */
594static
596 SCIP* scip, /**< SCIP data structure */
597 SCIP_CONS* cons, /**< xor constraint */
598 SCIP_VAR* var /**< variable to add to the constraint */
599 )
600{
601 SCIP_CONSDATA* consdata;
602 SCIP_Bool transformed;
603
604 assert(var != NULL);
605
606 consdata = SCIPconsGetData(cons);
607 assert(consdata != NULL);
608 assert(consdata->rows[0] == NULL);
609
610 /* are we in the transformed problem? */
611 transformed = SCIPconsIsTransformed(cons);
612
613 /* always use transformed variables in transformed constraints */
614 if( transformed )
615 {
617 }
618 assert(var != NULL);
619 assert(transformed == SCIPvarIsTransformed(var));
620
621 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
622 consdata->vars[consdata->nvars] = var;
623 consdata->nvars++;
624 consdata->sorted = (consdata->nvars == 1);
625 consdata->changed = TRUE;
626
627 /* install the rounding locks for the new variable */
628 SCIP_CALL( lockRounding(scip, cons, var) );
629
630 /* we only catch this event in presolving stages
631 * we need to catch this event also during exiting presolving because we call applyFixings to clean up the constraint
632 * and this can lead to an insertion of a replacement of variables for which we will try to drop the VARFIXED event.
633 */
636 {
637 SCIP_CONSHDLRDATA* conshdlrdata;
638 SCIP_CONSHDLR* conshdlr;
639
641 assert(conshdlr != NULL);
642 conshdlrdata = SCIPconshdlrGetData(conshdlr);
643 assert(conshdlrdata != NULL);
644
645 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
646 (SCIP_EVENTDATA*)consdata, NULL) );
647 }
648
649 /**@todo update LP rows */
650 if( consdata->rows[0] != NULL )
651 {
652 SCIPerrorMessage("cannot add coefficients to xor constraint after LP relaxation was created\n");
653 return SCIP_INVALIDCALL;
654 }
655
656 return SCIP_OKAY;
657}
658
659/** deletes coefficient at given position from xor constraint data */
660static
662 SCIP* scip, /**< SCIP data structure */
663 SCIP_CONS* cons, /**< xor constraint */
664 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
665 int pos /**< position of coefficient to delete */
666 )
667{
668 SCIP_CONSDATA* consdata;
669
670 assert(eventhdlr != NULL);
671
672 consdata = SCIPconsGetData(cons);
673 assert(consdata != NULL);
674 assert(0 <= pos && pos < consdata->nvars);
675 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
676
677 /* remove the rounding locks of the deleted variable */
678 SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
679
680 /* we only catch this event in presolving stage, so we need to only drop it there */
683 {
684 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_VARFIXED, eventhdlr,
685 (SCIP_EVENTDATA*)consdata, -1) );
686 }
687
688 if( SCIPconsIsTransformed(cons) )
689 {
690 /* if the position is watched, stop watching the position */
691 if( consdata->watchedvar1 == pos )
692 {
693 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar2, -1) );
694 }
695 if( consdata->watchedvar2 == pos )
696 {
697 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar1, -1) );
698 }
699 }
700 assert(pos != consdata->watchedvar1);
701 assert(pos != consdata->watchedvar2);
702
703 /* move the last variable to the free slot */
704 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
705 consdata->nvars--;
706
707 /* if the last variable (that moved) was watched, update the watched position */
708 if( consdata->watchedvar1 == consdata->nvars )
709 consdata->watchedvar1 = pos;
710 if( consdata->watchedvar2 == consdata->nvars )
711 consdata->watchedvar2 = pos;
712
713 consdata->propagated = FALSE;
714 consdata->sorted = FALSE;
715 consdata->changed = TRUE;
716
717 return SCIP_OKAY;
718}
719
720/** sorts and constraint's variables by non-decreasing variable index */
721static
723 SCIP_CONSDATA* consdata /**< constraint data */
724 )
725{
726 assert(consdata != NULL);
727
728 if( !consdata->sorted )
729 {
730 if( consdata->nvars <= 1 )
731 consdata->sorted = TRUE;
732 else
733 {
734 SCIP_VAR* var1 = NULL;
735 SCIP_VAR* var2 = NULL;
736
737 /* remember watch variables */
738 if( consdata->watchedvar1 != -1 )
739 {
740 var1 = consdata->vars[consdata->watchedvar1];
741 assert(var1 != NULL);
742 consdata->watchedvar1 = -1;
743 if( consdata->watchedvar2 != -1 )
744 {
745 var2 = consdata->vars[consdata->watchedvar2];
746 assert(var2 != NULL);
747 consdata->watchedvar2 = -1;
748 }
749 }
750 assert(consdata->watchedvar1 == -1);
751 assert(consdata->watchedvar2 == -1);
752 assert(var1 != NULL || var2 == NULL);
753
754 /* sort variables after index */
755 SCIPsortPtr((void**)consdata->vars, SCIPvarCompActiveAndNegated, consdata->nvars);
756 consdata->sorted = TRUE;
757
758 /* correct watched variables */
759 if( var1 != NULL )
760 {
761 int v;
762
763 /* since negated variables exist, we need to loop over all variables to find the old variable and cannot use
764 * SCIPsortedvecFindPtr()
765 */
766 for( v = consdata->nvars - 1; v >= 0; --v )
767 {
768 if( consdata->vars[v] == var1 )
769 {
770 consdata->watchedvar1 = v;
771 if( var2 == NULL || consdata->watchedvar2 != -1 )
772 break;
773 }
774 else if( consdata->vars[v] == var2 )
775 {
776 assert(consdata->vars[v] != NULL);
777 consdata->watchedvar2 = v;
778 if( consdata->watchedvar1 != -1 )
779 break;
780 }
781 }
782 assert(consdata->watchedvar1 != -1);
783 assert(consdata->watchedvar2 != -1 || var2 == NULL);
784 assert(consdata->watchedvar1 < consdata->nvars);
785 assert(consdata->watchedvar2 < consdata->nvars);
786 }
787 }
788 }
789
790#ifdef SCIP_DEBUG
791 /* check sorting */
792 {
793 int v;
794
795 for( v = 0; v < consdata->nvars; ++v )
796 {
797 assert(v == consdata->nvars-1 || SCIPvarCompareActiveAndNegated(consdata->vars[v], consdata->vars[v+1]) <= 0);
798 }
799 }
800#endif
801}
802
803
804/** gets the key of the given element */
805static
807{ /*lint --e{715}*/
808 /* the key is the element itself */
809 return elem;
810}
811
812/** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
813static
815{
818 int i;
819#ifndef NDEBUG
820 SCIP* scip;
821
822 scip = (SCIP*)userptr;
823 assert(scip != NULL);
824#endif
825
828
829 /* checks trivial case */
830 if( consdata1->nvars != consdata2->nvars )
831 return FALSE;
832
833 /* sorts the constraints */
836 assert(consdata1->sorted);
837 assert(consdata2->sorted);
838
839 for( i = 0; i < consdata1->nvars ; ++i )
840 {
841 /* tests if variables are equal */
842 if( consdata1->vars[i] != consdata2->vars[i] )
843 {
844 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
845 SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
846 return FALSE;
847 }
849 }
850
851 return TRUE;
852}
853
854/** returns the hash value of the key */
855static
857{ /*lint --e{715}*/
858 SCIP_CONSDATA* consdata;
859 int minidx;
860 int mididx;
861 int maxidx;
862
863 consdata = SCIPconsGetData((SCIP_CONS*)key);
864 assert(consdata != NULL);
865 assert(consdata->sorted);
866 assert(consdata->nvars > 0);
867
868 /* only active, fixed or negated variables are allowed */
869 assert(consdata->vars[0] != NULL);
870 assert(consdata->vars[consdata->nvars / 2] != NULL);
871 assert(consdata->vars[consdata->nvars - 1] != NULL);
872 assert(SCIPvarIsActive(consdata->vars[0]) || SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_FIXED);
873 assert(SCIPvarIsActive(consdata->vars[consdata->nvars / 2]) || SCIPvarGetStatus(consdata->vars[consdata->nvars / 2]) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(consdata->vars[consdata->nvars / 2]) == SCIP_VARSTATUS_FIXED);
874 assert(SCIPvarIsActive(consdata->vars[consdata->nvars - 1]) || SCIPvarGetStatus(consdata->vars[consdata->nvars - 1]) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(consdata->vars[consdata->nvars - 1]) == SCIP_VARSTATUS_FIXED);
875
876 minidx = SCIPvarGetIndex(consdata->vars[0]);
877 mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
878 maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
879 /* note that for all indices it does not hold that they are sorted, because variables are sorted with
880 * SCIPvarCompareActiveAndNegated (see var.c)
881 */
882
883 return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
884}
885
886/** deletes all fixed variables and all pairs of equal variables */
887static
889 SCIP* scip, /**< SCIP data structure */
890 SCIP_CONS* cons, /**< xor constraint */
891 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
892 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
893 int* naggrvars, /**< pointer to add up the number of aggregated variables */
894 int* naddconss, /**< pointer to add up the number of added constraints */
895 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
896 )
897{
898 SCIP_CONSDATA* consdata;
899 int v;
900
901 consdata = SCIPconsGetData(cons);
902 assert(consdata != NULL);
903 assert(consdata->nvars == 0 || consdata->vars != NULL);
904 assert(nchgcoefs != NULL);
905
906 SCIPdebugMsg(scip, "before fixings: ");
908
909 v = 0;
910 while( v < consdata->nvars )
911 {
912 SCIP_VAR* var;
913
914 var = consdata->vars[v];
916
917 if( SCIPvarGetUbGlobal(var) < 0.5 )
918 {
920 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
921 (*nchgcoefs)++;
922 }
923 else if( SCIPvarGetLbGlobal(var) > 0.5 && consdata->deleteintvar )
924 {
926 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
927 consdata->rhs = !consdata->rhs;
928 (*nchgcoefs)++;
929 }
930 else
931 {
933 SCIP_Bool negated;
934
935 /* get binary representative of variable */
937
938 /* remove all negations by replacing them with the active variable
939 * it holds that xor(x1, ~x2) = 0 <=> xor(x1, x2) = 1
940 * @note this can only be done if the integer variable does not exist
941 */
942 if( negated && consdata->intvar == NULL )
943 {
945
947 consdata->rhs = !consdata->rhs;
948 }
949
950 /* check, if the variable should be replaced with the representative */
951 if( repvar != var )
952 {
953 /* delete old (aggregated) variable */
954 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
955
956 /* add representative instead */
957 SCIP_CALL( addCoef(scip, cons, repvar) );
958 }
959 else
960 ++v;
961 }
962 }
963
964 /* sort the variables in the constraint */
965 consdataSort(consdata);
966 assert(consdata->sorted);
967
968 SCIPdebugMsg(scip, "after sort : ");
970
971 /* delete pairs of equal or negated variables; scan from back to front because deletion doesn't affect the
972 * order of the front variables
973 */
974 v = consdata->nvars-2;
975 while ( v >= 0 )
976 {
977 if( consdata->vars[v] == consdata->vars[v+1] ) /*lint !e679*/
978 {
979 SCIP_VAR* newvars[3];
980 SCIP_Real vals[3];
981
982 newvars[2] = consdata->vars[v];
983 vals[2] = 1.0;
984
985 /* delete both variables */
986 SCIPdebugMsg(scip, "xor constraint <%s>: deleting pair of equal variables <%s>\n",
987 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]));
988 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v+1) );
989 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
990 (*nchgcoefs) += 2;
991 v = MIN(v, consdata->nvars-1);
992
993 /* need to update integer variable, consider the following case:
994 * xor(x1, x2, x3, x4, x5) = 0 (and x1 == x2) was change above to
995 * xor( x3, x4, x5) = 0
996 * assuming we have an integer variable y it needs to be replaced by z with y = x1 + z and
997 * z in [max(lb_y-ub_x1, 0), ub_y-lb_x1]
998 */
999 if( consdata->intvar != NULL )
1000 {
1002 SCIP_Real lb;
1003 SCIP_Real ub;
1004 SCIP_VARTYPE vartype;
1005 char varname[SCIP_MAXSTRLEN];
1006 char consname[SCIP_MAXSTRLEN];
1007
1008 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "agg_%s", SCIPvarGetName(consdata->intvar));
1009 lb = MAX(SCIPvarGetLbGlobal(consdata->intvar) - SCIPvarGetUbGlobal(newvars[2]), 0); /*lint !e666*/
1010 ub = MAX(SCIPvarGetUbGlobal(consdata->intvar) - SCIPvarGetLbGlobal(newvars[2]), 0); /*lint !e666*/
1011 vartype = SCIPvarGetType(consdata->intvar);
1012
1013 SCIP_CALL( SCIPcreateVar(scip, &newvars[0], varname, lb, ub, 0.0, vartype,
1014 SCIPvarIsInitial(consdata->intvar), SCIPvarIsRemovable(consdata->intvar),
1015 NULL, NULL, NULL, NULL, NULL) );
1016 SCIP_CALL( SCIPaddVar(scip, newvars[0]) );
1017 vals[0] = 1.0;
1018
1019 newvars[1] = consdata->intvar;
1020 vals[1] = -1.0;
1021
1022 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons));
1023
1024 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 3, newvars, vals, 0.0, 0.0,
1025 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), TRUE, /*SCIPconsIsEnforced(cons),*/
1026 TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
1029
1032 ++(*naddconss);
1033
1034 SCIP_CALL( setIntvar(scip, cons, newvars[0]) );
1035 SCIP_CALL( SCIPreleaseVar(scip, &newvars[0]) );
1036 }
1037 }
1038 else if( consdata->vars[v] == SCIPvarGetNegatedVar(consdata->vars[v+1]) ) /*lint !e679*/
1039 {
1040 /* delete both variables and negate the rhs */
1041 SCIPdebugMsg(scip, "xor constraint <%s>: deleting pair of negated variables <%s> and <%s>\n",
1042 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[v+1])); /*lint !e679*/
1043 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v+1) );
1044 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1045 (*nchgcoefs) += 2;
1046 consdata->rhs = !consdata->rhs;
1047 v = MIN(v, consdata->nvars-1);
1048
1049 /* need to update integer variable, consider the following case:
1050 * xor(x1, x2, x3, x4, x5) = 0 (and x1 = ~x2) was change above to
1051 * xor( x3, x4, x5) = 1
1052 * assuming we have an integer variable y it needs to be replaced by z with y = 1 + z and z in [max(lb_y - 1, 0), ub_y - 1]
1053 */
1054 if( consdata->rhs && consdata->intvar != NULL )
1055 {
1057 SCIP_Real lb;
1058 SCIP_Real ub;
1059 SCIP_VARTYPE vartype;
1060 char varname[SCIP_MAXSTRLEN];
1061 SCIP_Bool aggregated;
1062 SCIP_Bool infeasible;
1063 SCIP_Bool redundant;
1064
1065 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "agg_%s", SCIPvarGetName(consdata->intvar));
1066 /* avoid infeasible cutoffs and guarantee non-negative bounds for the new artificial integer variable */
1067 lb = MAX(SCIPvarGetLbGlobal(consdata->intvar) - 1, 0); /*lint !e666*/
1068 ub = MAX(SCIPvarGetUbGlobal(consdata->intvar) - 1, 0); /*lint !e666*/
1069 vartype = (lb == 0 && ub == 1) ? SCIP_VARTYPE_BINARY : SCIPvarGetType(consdata->intvar);
1070
1071 SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, lb, ub, 0.0, vartype,
1072 SCIPvarIsInitial(consdata->intvar), SCIPvarIsRemovable(consdata->intvar),
1073 NULL, NULL, NULL, NULL, NULL) );
1075
1076 SCIP_CALL( SCIPaggregateVars(scip, consdata->intvar, newvar, 1.0, -1.0, 1.0, &infeasible, &redundant, &aggregated) );
1077 assert(infeasible || redundant || SCIPdoNotAggr(scip));
1078
1079 if( infeasible )
1080 {
1082 *cutoff = TRUE;
1083 break;
1084 }
1085
1086 if( aggregated )
1087 {
1088 (*naggrvars)++;
1089
1090 if( SCIPvarIsActive(newvar) )
1091 {
1092 SCIP_CALL( setIntvar(scip, cons, newvar) );
1094 }
1095 /* the new variable should only by inactive if it was fixed due to the aggregation, so also the old variable
1096 * should be fixed now.
1097 *
1098 * @todo if newvar is not active we may want to transform the xor into a linear constraint
1099 */
1100 else
1101 {
1103 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->intvar), SCIPvarGetUbGlobal(consdata->intvar)));
1104
1105 SCIP_CALL( setIntvar(scip, cons, newvar) );
1107 }
1108 }
1109 else
1110 {
1112 char consname[SCIP_MAXSTRLEN];
1113 SCIP_VAR* newvars[2];
1114 SCIP_Real vals[2];
1115
1116 newvars[0] = consdata->intvar;
1117 vals[0] = 1.0;
1118 newvars[1] = newvar;
1119 vals[1] = -1.0;
1120
1121 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons));
1122
1123 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, newvars, vals, 1.0, 1.0,
1124 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), TRUE, /*SCIPconsIsEnforced(cons),*/
1125 TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
1128
1131 ++(*naddconss);
1132
1133 SCIP_CALL( setIntvar(scip, cons, newvar) );
1135 }
1136 }
1137 }
1138 else
1139 assert(SCIPvarGetProbvar(consdata->vars[v]) != SCIPvarGetProbvar(consdata->vars[v+1])); /*lint !e679*/
1140 --v;
1141 }
1142
1143 SCIPdebugMsg(scip, "after fixings : ");
1144 SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
1145
1146 return SCIP_OKAY;
1147}
1148
1149/** adds extended flow formulation
1150 *
1151 * The extended flow formulation is built as follows: Let \f$x_1, \dots, x_k\f$ be the variables contained in the given
1152 * XOR constraint. We construct a two layered flow network. The upper layer is called the north layer and the lower is
1153 * called the south layer. For each \f$x_i,\; i = 2, \ldots, k-1\f$, we add arcs that stay in the north and south layer
1154 * (denoted by 'nn' and 'ss', respectively), as well as arcs that change the layers (denoted by 'ns' and 'sn'). For
1155 * \f$x_1\f$, we only add two arcs from the source to the two layers. The source is located on the north layer. For
1156 * \f$x_k\f$, we add two arcs connecting the two layers to the sink. Depending on the rhs of the constraint the sink is
1157 * located on the north or south layer. A change in the layers corresponds to a parity change, i.e., the corresponding
1158 * variable \f$x_i\f$ is 1 (and 0 otherwise).
1159 */
1160static
1162 SCIP* scip, /**< SCIP data structure */
1163 SCIP_CONS* cons, /**< constraint to check */
1164 int* naggrvars, /**< pointer to add up the number of aggregated variables */
1165 int* naddedconss /**< number of added constraints */
1166 )
1167{
1168 char name[SCIP_MAXSTRLEN];
1169 SCIP_CONSDATA* consdata;
1174 SCIP_VAR* vars[4];
1175 SCIP_Real vals[4];
1176 int i;
1177
1178 assert( scip != NULL );
1179 assert( cons != NULL );
1180 assert( naddedconss != NULL );
1181 *naddedconss = 0;
1182
1183 /* exit if contraints is modifiable */
1184 if ( SCIPconsIsModifiable(cons) )
1185 return SCIP_OKAY;
1186
1187 consdata = SCIPconsGetData(cons);
1188 assert( consdata != NULL );
1189
1190 /* exit if extended formulation has been added already */
1191 if ( consdata->extvars != NULL )
1192 return SCIP_OKAY;
1193
1194 /* xor constraints with at most 3 variables are handled directly through rows for the convex hull */
1195 if ( consdata->nvars <= 3 )
1196 return SCIP_OKAY;
1197
1198 SCIPdebugMsg(scip, "Add extended formulation for xor constraint <%s> ...\n", SCIPconsGetName(cons));
1199 assert( consdata->extvars == NULL );
1200 assert( consdata->nextvars == 0 );
1201 assert( consdata->extvarssize == 0 );
1202
1203 /* get storage for auxiliary variables */
1204 consdata->extvarssize = 4 * (consdata->nvars);
1205 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->extvars), consdata->extvarssize) );
1206
1207 /* pass through components */
1208 for (i = 0; i < consdata->nvars; ++i)
1209 {
1210 /* variables: n - north, s - south */
1211 SCIP_VAR* varnn = NULL;
1212 SCIP_VAR* varns = NULL;
1213 SCIP_VAR* varsn = NULL;
1214 SCIP_VAR* varss = NULL;
1216 SCIP_Real rhs = 0.0;
1217 SCIP_Bool infeasible = FALSE;
1218 SCIP_Bool redundant = FALSE;
1219 SCIP_Bool aggregated = FALSE;
1220 int cnt = 0;
1221
1222 /* create variables */
1223 if ( i == 0 )
1224 {
1225 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1228
1229 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1232
1233 /* need to lock variables, because we aggregate them */
1236
1237 /* aggregate ns variable with original variable */
1238 SCIP_CALL( SCIPaggregateVars(scip, varns, consdata->vars[0], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1239 assert( ! infeasible );
1240 assert( redundant );
1241 assert( aggregated );
1242 ++(*naggrvars);
1243 }
1244 else
1245 {
1246 if ( i == consdata->nvars-1 )
1247 {
1248 if ( consdata->rhs )
1249 {
1250 /* if the rhs is 1 (true) the flow goes to the bottom level */
1251 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1254
1255 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ss", SCIPconsGetName(cons), i);
1258
1259 /* need to lock variables, because we aggregate them */
1262
1263 /* aggregate ns variable with original variable */
1264 SCIP_CALL( SCIPaggregateVars(scip, varns, consdata->vars[i], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1265 assert( ! infeasible );
1266 assert( redundant );
1267 assert( aggregated );
1268 ++(*naggrvars);
1269 }
1270 else
1271 {
1272 /* if the rhs is 0 (false) the flow stays on the top level */
1273 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1276
1277 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_sn", SCIPconsGetName(cons), i);
1280
1281 /* need to lock variables, because we aggregate them */
1284
1285 /* aggregate sn variable with original variable */
1286 SCIP_CALL( SCIPaggregateVars(scip, varsn, consdata->vars[i], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1287 assert( ! infeasible );
1288 assert( redundant );
1289 assert( aggregated );
1290 ++(*naggrvars);
1291 }
1292 }
1293 else
1294 {
1295 /* add the four flow variables */
1296 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1299
1300 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1303
1304 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_sn", SCIPconsGetName(cons), i);
1307
1308 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ss", SCIPconsGetName(cons), i);
1311
1316
1317 /* add coupling constraint */
1318 cnt = 0;
1319 if ( varns != NULL )
1320 {
1321 vars[cnt] = varns;
1322 vals[cnt++] = 1.0;
1323 }
1324 if ( varsn != NULL )
1325 {
1326 vars[cnt] = varsn;
1327 vals[cnt++] = 1.0;
1328 }
1329 assert( SCIPvarIsTransformed(consdata->vars[i]) );
1330 vars[cnt] = consdata->vars[i];
1331 vals[cnt++] = -1.0;
1332
1333 assert( cnt >= 2 );
1334 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_couple", SCIPconsGetName(cons));
1335 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1336 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, 0.0, 0.0,
1341 ++(*naddedconss);
1342 }
1343
1344 /* add south flow conservation constraint */
1345
1346 /* incoming variables */
1347 cnt = 0;
1348 if ( varprevss != NULL )
1349 {
1350 vars[cnt] = varprevss;
1351 vals[cnt++] = 1.0;
1352 }
1353 if ( varprevns != NULL )
1354 {
1355 vars[cnt] = varprevns;
1356 vals[cnt++] = 1.0;
1357 }
1358
1359 /* outgoing variables */
1360 if ( varss != NULL )
1361 {
1362 vars[cnt] = varss;
1363 vals[cnt++] = -1.0;
1364 }
1365 if ( varsn != NULL )
1366 {
1367 vars[cnt] = varsn;
1368 vals[cnt++] = -1.0;
1369 }
1370
1371 assert( cnt >= 2 );
1372 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_south", SCIPconsGetName(cons));
1373 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1374 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, 0.0, 0.0,
1379 ++(*naddedconss);
1380 }
1381
1382 /* add north flow conservation constraint */
1383
1384 /* incoming variables */
1385 cnt = 0;
1386 if ( varprevnn != NULL )
1387 {
1388 vars[cnt] = varprevnn;
1389 vals[cnt++] = 1.0;
1390 }
1391 if ( varprevsn != NULL )
1392 {
1393 vars[cnt] = varprevsn;
1394 vals[cnt++] = 1.0;
1395 }
1396
1397 /* outgoing variables */
1398 if ( varnn != NULL )
1399 {
1400 vars[cnt] = varnn;
1401 vals[cnt++] = -1.0;
1402 }
1403 if ( varns != NULL )
1404 {
1405 vars[cnt] = varns;
1406 vals[cnt++] = -1.0;
1407 }
1408
1409 assert( cnt >= 2 );
1410 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_north", SCIPconsGetName(cons));
1411 if ( i == 0 )
1412 rhs = -1.0;
1413 else
1414 rhs = 0.0;
1415
1416 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1417 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, rhs, rhs,
1422 ++(*naddedconss);
1423
1424 /* store variables */
1425 consdata->extvars[4*i] = varnn; /*lint !e679*/
1426 consdata->extvars[4*i + 1] = varns; /*lint !e679*/
1427 consdata->extvars[4*i + 2] = varsn; /*lint !e679*/
1428 consdata->extvars[4*i + 3] = varss; /*lint !e679*/
1429
1430 if ( varnn != NULL )
1431 ++(consdata->nextvars);
1432 if ( varns != NULL )
1433 ++(consdata->nextvars);
1434 if ( varsn != NULL )
1435 ++(consdata->nextvars);
1436 if ( varss != NULL )
1437 ++(consdata->nextvars);
1438
1439 /* store previous variables */
1440 varprevnn = varnn;
1441 varprevns = varns;
1442 varprevsn = varsn;
1443 varprevss = varss;
1444 }
1445
1446 return SCIP_OKAY;
1447}
1448
1449/** adds extended asymmetric formulation
1450 *
1451 * The extended asymmetric formulation is constructed as follows: Let \f$x_1, \dots, x_k\f$ be the variables contained
1452 * in the given XOR constraint. We introduce variables \f$p_1, \ldots, p_k\f$ with the following constraints: \f$p_1 =
1453 * x_1\f$, \f$p_k = 1\f$, and for \f$i = 2, \ldots, k-1\f$:
1454 * \f[
1455 * \begin{array}{ll}
1456 * p_i & \leq p_{i-1} + x_i\\
1457 * p_i & \leq 2 - (p_{i-1} + x_i)\\
1458 * p_i & \geq p_{i-1} - x_i\\
1459 * p_i & \geq x_i - p_{i-1}.
1460 * \end{array}
1461 * \f]
1462 * This formulation is described in
1463 *
1464 * Robert D. Carr and Goran Konjevod@n
1465 * Polyhedral combinatorics@n
1466 * In Harvey Greenberg, editor, Tutorials on emerging methodologies and applications in Operations Research,@n
1467 * Chapter 2, pages (2-1)-(2-48). Springer, 2004.
1468 */
1469static
1471 SCIP* scip, /**< SCIP data structure */
1472 SCIP_CONS* cons, /**< constraint to check */
1473 int* naggrvars, /**< pointer to add up the number of aggregated variables */
1474 int* naddedconss /**< number of added constraints */
1475 )
1476{
1477 char name[SCIP_MAXSTRLEN];
1478 SCIP_CONSDATA* consdata;
1479 SCIP_VAR* vars[3];
1480 SCIP_Real vals[3];
1482 int i;
1483
1484 assert( scip != NULL );
1485 assert( cons != NULL );
1486 assert( naddedconss != NULL );
1487 *naddedconss = 0;
1488
1489 /* exit if contraints is modifiable */
1490 if ( SCIPconsIsModifiable(cons) )
1491 return SCIP_OKAY;
1492
1493 consdata = SCIPconsGetData(cons);
1494 assert( consdata != NULL );
1495
1496 /* exit if extended formulation has been added already */
1497 if ( consdata->extvars != NULL )
1498 return SCIP_OKAY;
1499
1500 /* xor constraints with at most 3 variables are handled directly through rows for the convex hull */
1501 if ( consdata->nvars <= 3 )
1502 return SCIP_OKAY;
1503
1504 SCIPdebugMsg(scip, "Add extended formulation for xor constraint <%s> ...\n", SCIPconsGetName(cons));
1505 assert( consdata->extvars == NULL );
1506 assert( consdata->nextvars == 0 );
1507
1508 /* get storage for auxiliary variables */
1509 consdata->extvarssize = consdata->nvars;
1510 consdata->nextvars = consdata->nvars;
1511 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->extvars), consdata->extvarssize ) );
1512
1513 /* pass through components */
1514 for (i = 0; i < consdata->nvars; ++i)
1515 {
1516 SCIP_Bool infeasible = FALSE;
1517 SCIP_Bool redundant = FALSE;
1518 SCIP_Bool aggregated = FALSE;
1520 SCIP_VAR* artvar = NULL;
1521 SCIP_Real lb = 0.0;
1522 SCIP_Real ub = 1.0;
1523
1524 /* determine fixing for last variables */
1525 if ( i == consdata->nvars-1 )
1526 {
1527 if ( consdata->rhs )
1528 {
1529 lb = 1.0;
1530 ub = 1.0;
1531 }
1532 else
1533 {
1534 lb = 0.0;
1535 ub = 0.0;
1536 }
1537 }
1538
1539 /* create variable */
1540 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "p_%s_%d", SCIPconsGetName(cons), i);
1544
1545 /* create constraints */
1546 if ( i == 0 )
1547 {
1548 /* aggregate artificial variable with original variable */
1549 SCIP_CALL( SCIPaggregateVars(scip, artvar, consdata->vars[0], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1550 assert( ! infeasible );
1551 assert( redundant );
1552 assert( aggregated );
1553 ++(*naggrvars);
1554 }
1555 else
1556 {
1557 assert( SCIPvarIsTransformed(consdata->vars[i]) );
1558
1559 /* add first constraint */
1560 vars[0] = artvar;
1561 vals[0] = 1.0;
1562 vars[1] = prevvar;
1563 vals[1] = -1.0;
1564 vars[2] = consdata->vars[i];
1565 vals[2] = -1.0;
1566
1567 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_1", SCIPconsGetName(cons), i);
1568 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1569 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1574 ++(*naddedconss);
1575
1576 /* add second constraint */
1577 vars[0] = artvar;
1578 vals[0] = 1.0;
1579 vars[1] = prevvar;
1580 vals[1] = 1.0;
1581 vars[2] = consdata->vars[i];
1582 vals[2] = 1.0;
1583
1584 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_2", SCIPconsGetName(cons), i);
1585 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1586 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 2.0,
1591 ++(*naddedconss);
1592
1593 /* add third constraint */
1594 vars[0] = artvar;
1595 vals[0] = -1.0;
1596 vars[1] = prevvar;
1597 vals[1] = 1.0;
1598 vars[2] = consdata->vars[i];
1599 vals[2] = -1.0;
1600
1601 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_3", SCIPconsGetName(cons), i);
1602 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1603 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1608 ++(*naddedconss);
1609
1610 /* add fourth constraint */
1611 vars[0] = artvar;
1612 vals[0] = -1.0;
1613 vars[1] = prevvar;
1614 vals[1] = -1.0;
1615 vars[2] = consdata->vars[i];
1616 vals[2] = 1.0;
1617
1618 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_4", SCIPconsGetName(cons), i);
1619 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1620 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1625 ++(*naddedconss);
1626 }
1627
1628 /* store variable */
1629 consdata->extvars[i] = artvar;
1630 prevvar = artvar;
1631 }
1632
1633 return SCIP_OKAY;
1634}
1635
1636/** creates LP row corresponding to xor constraint:
1637 * x1 + ... + xn - 2q == rhs
1638 * with internal integer variable q;
1639 * in the special case of 3 variables and c = 0, the following linear system is created:
1640 * + x - y - z <= 0
1641 * - x + y - z <= 0
1642 * - x - y + z <= 0
1643 * + x + y + z <= 2
1644 * in the special case of 3 variables and c = 1, the following linear system is created:
1645 * - x + y + z <= 1
1646 * + x - y + z <= 1
1647 * + x + y - z <= 1
1648 * - x - y - z <= -1
1649 */
1650static
1652 SCIP* scip, /**< SCIP data structure */
1653 SCIP_CONS* cons /**< constraint to check */
1654 )
1655{
1656 SCIP_CONSDATA* consdata;
1657 char varname[SCIP_MAXSTRLEN];
1658
1659 consdata = SCIPconsGetData(cons);
1660 assert(consdata != NULL);
1661 assert(consdata->rows[0] == NULL);
1662
1663 if( SCIPconsIsModifiable(cons) || consdata->nvars != 3 )
1664 {
1665 SCIP_Real rhsval;
1666
1667 /* create internal variable, if not yet existing */
1668 if( consdata->intvar == NULL )
1669 {
1670 int ub;
1671
1672 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "XOR_artificial_%s_int", SCIPconsGetName(cons));
1673 ub = consdata->nvars/2;
1674 SCIP_CALL( SCIPcreateVar(scip, &consdata->intvar, varname, 0.0, (SCIP_Real)ub, 0.0,
1675 consdata->nvars >= 4 ? SCIP_VARTYPE_INTEGER : SCIP_VARTYPE_BINARY,
1677 SCIP_CALL( SCIPaddVar(scip, consdata->intvar) );
1678
1679#ifdef WITH_DEBUG_SOLUTION
1681 {
1682 SCIP_Real solval;
1683 int count = 0;
1684 int v;
1685
1686 for( v = consdata->nvars - 1; v >= 0; --v )
1687 {
1688 SCIP_CALL( SCIPdebugGetSolVal(scip, consdata->vars[v], &solval) );
1689 count += (solval > 0.5 ? 1 : 0);
1690 }
1691 assert((count - consdata->rhs) % 2 == 0);
1692 solval = (SCIP_Real) ((count - consdata->rhs) / 2);
1693
1694 /* store debug sol value of artificial integer variable */
1695 SCIP_CALL( SCIPdebugAddSolVal(scip, consdata->intvar, solval) );
1696 }
1697#endif
1698
1699 /* install the rounding locks for the internal variable */
1700 SCIP_CALL( lockRounding(scip, cons, consdata->intvar) );
1701 }
1702
1703 /* create LP row */
1704 rhsval = (consdata->rhs ? 1.0 : 0.0);
1705 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[0], cons, SCIPconsGetName(cons), rhsval, rhsval,
1707 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[0], consdata->intvar, -2.0) );
1708 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[0], consdata->nvars, consdata->vars, 1.0) );
1709 }
1710 else if( !consdata->rhs )
1711 {
1712 char rowname[SCIP_MAXSTRLEN];
1713 int r;
1714
1715 /* create the <= 0 rows with one positive sign */
1716 for( r = 0; r < 3; ++r )
1717 {
1718 int v;
1719
1721 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[r], cons, rowname, -SCIPinfinity(scip), 0.0,
1723 for( v = 0; v < 3; ++v )
1724 {
1725 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[r], consdata->vars[v], v == r ? +1.0 : -1.0) );
1726 }
1727 }
1728
1729 /* create the <= 2 row with all positive signs */
1731 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[3], cons, rowname, -SCIPinfinity(scip), 2.0,
1733 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[3], consdata->nvars, consdata->vars, 1.0) );
1734
1735 /* create extra LP row if integer variable exists */
1736 if( consdata->intvar != NULL )
1737 {
1738 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[4], cons, SCIPconsGetName(cons), 0.0, 0.0,
1740 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[4], consdata->intvar, -2.0) );
1741 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[4], consdata->nvars, consdata->vars, 1.0) );
1742 }
1743 }
1744 else
1745 {
1746 char rowname[SCIP_MAXSTRLEN];
1747 int r;
1748
1749 /* create the <= 1 rows with one negative sign */
1750 for( r = 0; r < 3; ++r )
1751 {
1752 int v;
1753
1755 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[r], cons, rowname, -SCIPinfinity(scip), 1.0,
1757 for( v = 0; v < 3; ++v )
1758 {
1759 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[r], consdata->vars[v], v == r ? -1.0 : +1.0) );
1760 }
1761 }
1762
1763 /* create the <= -1 row with all negative signs */
1765 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[3], cons, rowname, -SCIPinfinity(scip), -1.0,
1767 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[3], consdata->nvars, consdata->vars, -1.0) );
1768
1769 /* create extra LP row if integer variable exists */
1770 if( consdata->intvar != NULL )
1771 {
1772 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[4], cons, SCIPconsGetName(cons), 1.0, 1.0,
1774 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[4], consdata->intvar, -2.0) );
1775 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[4], consdata->nvars, consdata->vars, 1.0) );
1776 }
1777 }
1778
1779 return SCIP_OKAY;
1780}
1781
1782/** adds linear relaxation of or constraint to the LP */
1783static
1785 SCIP* scip, /**< SCIP data structure */
1786 SCIP_CONS* cons, /**< constraint to check */
1787 SCIP_Bool* infeasible /**< pointer to store whether infeasibility was detected */
1788 )
1789{
1790 SCIP_CONSDATA* consdata;
1791 int r;
1792
1793 consdata = SCIPconsGetData(cons);
1794 assert(consdata != NULL);
1795 assert(infeasible != NULL);
1796 assert(!(*infeasible));
1797
1798 if( consdata->rows[0] == NULL )
1799 {
1801 }
1802 assert(consdata->rows[0] != NULL);
1803 for( r = 0; r < NROWS && !(*infeasible); ++r )
1804 {
1805 if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1806 {
1807 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, infeasible) );
1808 }
1809 }
1810
1811 return SCIP_OKAY;
1812}
1813
1814/** returns whether all rows of the LP relaxation are in the current LP */
1815static
1816SCIP_Bool allRowsInLP(
1817 SCIP_CONSDATA* consdata /**< constraint data */
1818 )
1819{
1820 assert(consdata != NULL);
1821
1822 if( consdata->rows[0] == NULL ) /* LP relaxation does not exist */
1823 return FALSE;
1824 else
1825 {
1826 int r;
1827 for( r = 0; r < NROWS; ++r )
1828 {
1829 if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1830 return FALSE;
1831 }
1832 return TRUE;
1833 }
1834}
1835
1836/** checks xor constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
1837static
1839 SCIP* scip, /**< SCIP data structure */
1840 SCIP_CONS* cons, /**< constraint to check */
1841 SCIP_SOL* sol, /**< solution to check, NULL for current solution */
1842 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
1843 SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
1844 )
1845{
1846 SCIP_CONSDATA* consdata;
1847
1848 assert(violated != NULL);
1849
1850 consdata = SCIPconsGetData(cons);
1851 assert(consdata != NULL);
1852
1853 *violated = FALSE;
1854
1855 /* check feasibility of constraint if necessary */
1856 if( checklprows || !allRowsInLP(consdata) )
1857 {
1858 SCIP_Real solval;
1859 SCIP_Bool odd;
1860 int ones;
1861 int i;
1862
1863 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1864 * enforcement
1865 */
1866 if( sol == NULL )
1867 {
1868 SCIP_CALL( SCIPincConsAge(scip, cons) );
1869 }
1870
1871 /* check, if all variables and the rhs sum up to an even value */
1872 odd = consdata->rhs;
1873 ones = 0;
1874 for( i = 0; i < consdata->nvars; ++i )
1875 {
1876 solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
1877 assert(SCIPisFeasIntegral(scip, solval));
1878 odd = (odd != (solval > 0.5));
1879
1880 if( solval > 0.5 )
1881 ++ones;
1882 }
1883 if( odd )
1884 {
1885 *violated = TRUE;
1886
1887 /* only reset constraint age if we are in enforcement */
1888 if( sol == NULL )
1890 }
1891 else if( consdata->intvar != NULL )
1892 {
1893 solval = SCIPgetSolVal(scip, sol, consdata->intvar);
1894 assert(SCIPisFeasIntegral(scip, solval));
1895
1896 if( !SCIPisFeasEQ(scip, ones - 2 * solval, (SCIP_Real) consdata->rhs) )
1897 *violated = TRUE;
1898 }
1899
1900 /* only reset constraint age if we are in enforcement */
1901 if( *violated && sol == NULL )
1902 {
1904 }
1905 /* update constraint violation in solution */
1906 else if ( *violated && sol != NULL )
1908 }
1909
1910 return SCIP_OKAY;
1911}
1912
1913/** separates current LP solution
1914 *
1915 * Consider a XOR-constraint
1916 * \f[
1917 * x_1 \oplus x_2 \oplus \dots \oplus x_n = b
1918 * \f]
1919 * with \f$b \in \{0,1\}\f$ and a solution \f$x^*\f$ to be cut off. Small XOR constraints are handled by adding the
1920 * inequalities of the convex hull.
1921 *
1922 * The separation of larger XOR constraints has been described by @n
1923 * Xiaojie Zhang and Paul H. Siegel@n
1924 * "Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes"@n
1925 * IEEE Transactions on Information Theory, vol. 58, no. 10, 2012
1926 *
1927 * We separate the inequalities
1928 * \f[
1929 * \sum_{j \in S} (1 - x_j) + \sum_{j \notin S} x_j \geq 1
1930 * \f]
1931 * with \f$|S| \equiv (b+1) \mbox{ mod } 2\f$ as follows. That these inequalities are valid can be seen as follows: Let
1932 * \f$x\f$ be a feasible solution and suppose that the inequality is violated for some \f$S\f$. Then \f$x_j = 1\f$ for
1933 * all \f$j \in S\f$ and \f$x_j = 0\f$ for all \f$j \notin S\f$. Thus we should have
1934 * \f[
1935 * \oplus_{j \in S} x_j = |S| \mbox{ mod } 2 = b+1 \mbox{ mod } 2,
1936 * \f]
1937 * which is not equal to \f$b\f$ as required by the XOR-constraint.
1938 *
1939 * Let \f$L= \{j \;:\; x^*_j > \frac{1}{2}\}\f$. Suppose that \f$|L|\f$ has @em not the same parity as \f$b\f$ rhs. Then
1940 * \f[
1941 * \sum_{j \in L} (1 - x_j) + \sum_{j \notin L} x_j \geq 1
1942 * \f]
1943 * is the only inequality that can be violated. We rewrite the inequality as
1944 * \f[
1945 * \sum_{j \in L} x_j - \sum_{j \notin L} x_j \leq |L| - 1.
1946 * \f]
1947 * These inequalities are added.
1948 *
1949 * Otherwise let \f$k = \mbox{argmin}\{x^*_j \;:\; j \in L\}\f$ and check the inequality for \f$L \setminus \{k\}\f$
1950 * and similarly for \f$k = \mbox{argmax}\{x^*_j \;:\; j \in L\}\f$.
1951 */
1952static
1954 SCIP* scip, /**< SCIP data structure */
1955 SCIP_CONS* cons, /**< constraint to check */
1956 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1957 SCIP_Bool separateparity, /**< should parity inequalities be separated? */
1958 SCIP_Bool* separated, /**< pointer to store whether a cut was found */
1959 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1960 )
1961{
1962 SCIP_CONSDATA* consdata;
1963 SCIP_Real feasibility;
1964 int r;
1965
1966 assert( separated != NULL );
1967 assert( cutoff != NULL );
1968 *cutoff = FALSE;
1969
1970 consdata = SCIPconsGetData(cons);
1971 assert(consdata != NULL);
1972
1973 *separated = FALSE;
1974
1975 /* create row for the linear relaxation */
1976 if( consdata->rows[0] == NULL )
1977 {
1979 }
1980 assert(consdata->rows[0] != NULL);
1981
1982 /* test rows for feasibility and add it, if it is infeasible */
1983 for( r = 0; r < NROWS; ++r )
1984 {
1985 if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1986 {
1987 feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
1989 {
1990 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, cutoff) );
1991 if ( *cutoff )
1992 return SCIP_OKAY;
1993 *separated = TRUE;
1994 }
1995 }
1996 }
1997
1998 /* separate parity inequalities if required */
1999 if ( separateparity && consdata->nvars > 3 )
2000 {
2001 char name[SCIP_MAXSTRLEN];
2002 SCIP_Real maxval = -1.0;
2003 SCIP_Real minval = 2.0;
2004 SCIP_Real sum = 0.0;
2005 int maxidx = -1;
2006 int minidx = -1;
2007 int ngen = 0;
2008 int cnt = 0;
2009 int j;
2010
2011 SCIPdebugMsg(scip, "separating parity inequalities ...\n");
2012
2013 /* compute value */
2014 for (j = 0; j < consdata->nvars; ++j)
2015 {
2016 SCIP_Real val;
2017
2018 val = SCIPgetSolVal(scip, sol, consdata->vars[j]);
2019 if ( SCIPisFeasGT(scip, val, 0.5) )
2020 {
2021 if ( val < minval )
2022 {
2023 minval = val;
2024 minidx = j;
2025 }
2026 ++cnt;
2027 sum += (1.0 - val);
2028 }
2029 else
2030 {
2031 if ( val > maxval )
2032 {
2033 maxval = val;
2034 maxidx = j;
2035 }
2036 sum += val;
2037 }
2038 }
2039
2040 /* if size of set does not have the same parity as rhs (e.g., size is odd if rhs is 0) */
2041 if ( (cnt - (int) consdata->rhs) % 2 == 1 )
2042 {
2043 if ( SCIPisEfficacious(scip, 1.0 - sum) )
2044 {
2045 SCIP_ROW* row;
2046
2047 SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f)\n", 1.0 - sum);
2048
2049 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2050 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real) (cnt - 1), FALSE, FALSE, TRUE) );
2052
2053 /* fill in row */
2054 for (j = 0; j < consdata->nvars; ++j)
2055 {
2056 if ( SCIPisFeasGT(scip, SCIPgetSolVal(scip, sol, consdata->vars[j]), 0.5) )
2057 {
2058 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2059 }
2060 else
2061 {
2062 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2063 }
2064 }
2068 assert( SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real) (cnt-1)) );
2069 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2070 ++ngen;
2071 }
2072 }
2073 else
2074 {
2075 /* If the parity is equal: check removing the element with smallest value from the set and adding the
2076 * element with largest value to the set. If we remove the element with smallest value, we have to subtract (1
2077 * - minval) and add minval to correct the sum. */
2078 if ( SCIPisEfficacious(scip, 1.0 - (sum - 1.0 + 2.0 * minval)) )
2079 {
2080 SCIP_ROW* row;
2081
2082 SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f, minval: %f)\n", 1.0 - (sum - 1.0 + 2.0 * minval), minval);
2083
2084 /* the rhs of the inequality is the corrected set size minus 1 */
2085 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2086 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real) (cnt - 2), FALSE, FALSE, TRUE) );
2088
2089 /* fill in row */
2090 for (j = 0; j < consdata->nvars; ++j)
2091 {
2092 if ( SCIPisFeasGT(scip, SCIPgetSolVal(scip, sol, consdata->vars[j]), 0.5) )
2093 {
2094 /* if the index corresponds to the smallest element, we reverse the sign */
2095 if ( j == minidx )
2096 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2097 else
2098 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2099 }
2100 else
2101 {
2102 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2103 }
2104 }
2108 assert( SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real) (cnt-2)) );
2109 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2110 ++ngen;
2111 }
2112
2113 /* If we add the element with largest value, we have to add (1 - maxval) and subtract maxval to get the correct sum. */
2114 if ( SCIPisEfficacious(scip, 1.0 - (sum + 1.0 - 2.0 * maxval)) )
2115 {
2116 SCIP_ROW* row;
2117
2118 SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f, maxval: %f)\n", 1.0 - (sum + 1.0 - 2.0 * maxval), maxval);
2119
2120 /* the rhs of the inequality is the size of the corrected set */
2121 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2122 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real) cnt, FALSE, FALSE, TRUE) );
2124
2125 /* fill in row */
2126 for (j = 0; j < consdata->nvars; ++j)
2127 {
2128 if ( SCIPisFeasGT(scip, SCIPgetSolVal(scip, sol, consdata->vars[j]), 0.5) )
2129 {
2130 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2131 }
2132 else
2133 {
2134 /* if the index corresponds to the largest element, we reverse the sign */
2135 if ( j == maxidx )
2136 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2137 else
2138 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2139 }
2140 }
2144 assert( *cutoff || SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real)(j-1)) );
2145 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2146 ++ngen;
2147 }
2148 }
2149
2150 SCIPdebugMsg(scip, "separated parity inequalites: %d\n", ngen);
2151 if ( ngen > 0 )
2152 *separated = TRUE;
2153 }
2154
2155 return SCIP_OKAY;
2156}
2157
2158/** Transform linear system \f$A x = b\f$ into row echelon form via the Gauss algorithm with row pivoting over GF2
2159 * @returns the rank of @p A
2160 *
2161 * Here, \f$A \in R^{m \times n},\; b \in R^m\f$. On exit, the vector @p p contains a permutation of the row indices
2162 * used for pivoting and the function returns the rank @p r of @p A. For each row \f$i = 1, \ldots, r\f$, the entry @p
2163 * s[i] contains the column index of the first nonzero in row @p i.
2164 */
2165static
2167 SCIP* scip, /**< SCIP data structure */
2168 int m, /**< number of rows */
2169 int n, /**< number of columns */
2170 int* p, /**< row permutation */
2171 int* s, /**< steps indicators of the row echelon form */
2172 Type** A, /**< matrix */
2173 Type* b /**< rhs */
2174 )
2175{
2176 int pi;
2177 int i;
2178 int j;
2179 int k;
2180
2181 assert( A != NULL );
2182 assert( b != NULL );
2183 assert( p != NULL );
2184 assert( s != NULL );
2185
2186 /* init permutation and step indicators */
2187 for (i = 0; i < m; ++i)
2188 {
2189 p[i] = i;
2190 s[i] = i;
2191 }
2192
2193 /* loop through possible steps in echelon form (stop at min {n, m}) */
2194 for (i = 0; i < m && i < n; ++i)
2195 {
2196 assert( s[i] == i );
2197
2198 /* init starting column */
2199 if ( i == 0 )
2200 j = 0;
2201 else
2202 j = s[i-1] + 1;
2203
2204 /* find pivot row (i.e., first nonzero entry), if all entries in current row are 0 we search the next column */
2205 do
2206 {
2207 /* search in current column j */
2208 k = i;
2209 while ( k < m && A[p[k]][j] == 0 )
2210 ++k;
2211
2212 /* found pivot */
2213 if ( k < m )
2214 break;
2215
2216 /* otherwise search next column */
2217 ++j;
2218 }
2219 while ( j < n );
2220
2221 /* if not pivot entry was found (checked all columns), the rank of A is equal to the current index i; in this case
2222 * all entries in and below row i are 0 */
2223 if ( j >= n )
2224 return i;
2225
2226 /* at this place: we have found a pivot entry (p[k], j) */
2227 assert( k < m );
2228
2229 /* store step index */
2230 s[i] = j;
2231 assert( A[p[k]][j] != 0 );
2232
2233 /* swap row indices */
2234 if ( k != i )
2235 {
2236 int h = p[i];
2237 p[i] = p[k];
2238 p[k] = h;
2239 }
2240 pi = p[i];
2241 assert( A[pi][s[i]] != 0 );
2242
2243 /* do elimination */
2244 for (k = i+1; k < m; ++k)
2245 {
2246 int pk = p[k];
2247 /* if entry in leading column is nonzero (otherwise we already have a 0) */
2248 if ( A[pk][s[i]] != 0 )
2249 {
2250 for (j = s[i]; j < n; ++j)
2251 A[pk][j] = A[pk][j] ^ A[pi][j]; /*lint !e732*/
2252 b[pk] = b[pk] ^ b[pi]; /*lint !e732*/
2253 }
2254 }
2255
2256 /* check stopped (only every 100 rows in order to save time */
2257 if ( i % 100 == 99 )
2258 {
2259 if ( SCIPisStopped(scip) )
2260 return -1;
2261 }
2262 }
2263
2264 /* at this point we have treated all rows in which a step can occur; the rank is the minimum of the number of rows or
2265 * columns min {n,m}. */
2266 if ( n <= m )
2267 return n;
2268 return m;
2269}
2270
2271/** Construct solution from matrix in row echelon form over GF2
2272 *
2273 * Compute solution of \f$A x = b\f$, which is already in row echelon form (@see computeRowEchelonGF2()) */
2274static
2276 int m, /**< number of rows */
2277 int n, /**< number of columns */
2278 int r, /**< rank of matrix */
2279 int* p, /**< row permutation */
2280 int* s, /**< steps indicators of the row echelon form */
2281 Type** A, /**< matrix */
2282 Type* b, /**< rhs */
2283 Type* x /**< solution vector on exit */
2284 )
2285{
2286 int i;
2287 int k;
2288
2289 assert( A != NULL );
2290 assert( b != NULL );
2291 assert( s != NULL );
2292 assert( p != NULL );
2293 assert( x != NULL );
2294 assert( r <= m && r <= n );
2295
2296 /* init solution vector to 0 */
2297 for (k = 0; k < n; ++k)
2298 x[k] = 0;
2299
2300 /* loop backwards through solution vector */
2301 for (i = r-1; i >= 0; --i)
2302 {
2303 Type val;
2304
2305 assert( i <= s[i] && s[i] <= n );
2306
2307 /* init val with rhs and then add the contributions of the components of x already computed */
2308 val = b[p[i]];
2309 for (k = i+1; k < r; ++k)
2310 {
2311 assert( i <= s[k] && s[k] <= n );
2312 if ( A[p[i]][s[k]] != 0 )
2313 val = val ^ x[s[k]]; /*lint !e732*/
2314 }
2315
2316 /* store solution */
2317 x[s[i]] = val;
2318 }
2319}
2320
2321/** solve equation system over GF 2 by Gauss algorithm and create solution out of it or return cutoff
2322 *
2323 * Collect all information in xor constraints into a linear system over GF2. Then solve the system by computing a row
2324 * echelon form. If the system is infeasible, the current node is infeasible. Otherwise, we can compute a solution for
2325 * the xor constraints given. We check whether this gives a solution for the whole problem.
2326 *
2327 * We sort the columns with respect to the product of the objective coefficients and 1 minus the current LP solution
2328 * value. The idea is that columns that are likely to provide the steps in the row echelon form should appear towards
2329 * the front of the matrix. The smaller the product, the more it makes sense to set the variable to 1 (because the
2330 * solution value is already close to 1 and the objective function is small).
2331 *
2332 * Note that this function is called from propagation where usually no solution is available. However, the solution is
2333 * only used for sorting the columns. Thus, the procedure stays correct even with nonsense solutions.
2334 */
2335static
2337 SCIP* scip, /**< SCIP data structure */
2338 SCIP_CONS** conss, /**< xor constraints */
2339 int nconss, /**< number of xor constraints */
2340 SCIP_SOL* currentsol, /**< current solution (maybe NULL) */
2341 SCIP_RESULT* result /**< result of propagation (possibly cutoff, no change if primal solution has been tried) */
2342 )
2343{
2344 SCIP_CONSDATA* consdata;
2345 SCIP_HASHMAP* varhash;
2346 SCIP_Bool* xoractive;
2347 SCIP_Real* xorvals;
2348 SCIP_VAR** xorvars;
2349 SCIP_Bool noaggr = TRUE;
2350 Type** A;
2351 Type* b;
2352 int* s;
2353 int* p;
2354 int* xoridx;
2355 int* xorbackidx;
2356 int nconssactive = 0;
2357 int nconssmat = 0;
2358 int nvarsmat = 0;
2359 int nvars;
2360 int rank;
2361 int i;
2362 int j;
2363
2364 assert( scip != NULL );
2365 assert( conss != NULL );
2366 assert( result != NULL );
2367
2368 if ( *result == SCIP_CUTOFF )
2369 return SCIP_OKAY;
2370
2371 SCIPdebugMsg(scip, "Checking feasibility via the linear equation system over GF2 using Gauss.\n");
2372
2374
2375 /* set up hash map from variable to column index */
2381
2382 /* collect variables */
2383 for (i = 0; i < nconss; ++i)
2384 {
2385 int cnt = 0;
2386
2387 xoractive[i] = FALSE;
2388
2389 assert( conss[i] != NULL );
2390 consdata = SCIPconsGetData(conss[i]);
2391 assert( consdata != NULL );
2392
2393 /* count nonfixed variables in constraint */
2394 for (j = 0; j < consdata->nvars; ++j)
2395 {
2396 SCIP_VAR* var;
2397
2398 var = consdata->vars[j];
2399 assert( var != NULL );
2401
2402 /* replace negated variables */
2403 if ( SCIPvarIsNegated(var) )
2405 assert( var != NULL );
2406
2407 /* get the active variable */
2410 /* consider nonfixed variables */
2411 if ( var != NULL && SCIPcomputeVarLbLocal(scip, var) < 0.5 && SCIPcomputeVarUbLocal(scip, var) > 0.5 )
2412 {
2413 /* consider active variables and collect only new ones */
2414 if ( SCIPvarIsActive(var) && ! SCIPhashmapExists(varhash, var) )
2415 {
2416 /* add variable in map */
2418 assert( nvarsmat == SCIPhashmapGetImageInt(varhash, var) );
2419 xorvals[nvarsmat] = SCIPvarGetObj(var) * (1.0 - SCIPgetSolVal(scip, currentsol, var));
2420 xorvars[nvarsmat++] = var;
2421 }
2422 ++cnt;
2423 }
2424 }
2425
2426 if ( cnt > 0 )
2427 {
2428 xoractive[i] = TRUE;
2429 ++nconssactive;
2430 }
2431#ifdef SCIP_DISABLED_CODE
2432 /* The following can save time, if there are constraints with all variables fixed that are infeasible; this
2433 * should, however, be detected somewhere else, e.g., in propagateCons(). */
2434 else
2435 {
2436 /* all variables are fixed - check whether constraint is feasible (could be that the constraint is not propagated) */
2437 assert( cnt == 0 );
2438 for (j = 0; j < consdata->nvars; ++j)
2439 {
2440 /* count variables fixed to 1 */
2441 if ( SCIPcomputeVarLbLocal(scip, consdata->vars[j]) > 0.5 )
2442 ++cnt;
2443 else
2444 assert( SCIPcomputeVarUbLocal(scip, consdata->vars[j]) < 0.5 );
2445 }
2446 if ( ( cnt - consdata->rhs ) % 2 != 0 )
2447 {
2448 SCIPdebugMsg(scip, "constraint <%s> with all variables fixed is violated.\n", SCIPconsGetName(conss[i]));
2450 break;
2451 }
2452 }
2453#endif
2454 }
2455 assert( nvarsmat <= nvars );
2456 assert( nconssactive <= nconss );
2457
2459 {
2460 SCIPdebugMsg(scip, "Skip checking the xor system over GF2 (%d conss, %d vars).\n", nconssactive, nvarsmat);
2465 SCIPhashmapFree(&varhash);
2466 return SCIP_OKAY;
2467 }
2468
2469 /* init index */
2470 for (j = 0; j < nvarsmat; ++j)
2471 xoridx[j] = j;
2472
2473 /* Sort variables non-decreasingly with respect to product of objective and 1 minus the current solution value: the
2474 * smaller the value the better it would be to set the variable to 1. This is more likely if the variable appears
2475 * towards the front of the matrix, because only the entries on the steps in the row echelon form will have the
2476 * chance to be nonzero.
2477 */
2480
2481 /* build back index */
2483 for (j = 0; j < nvarsmat; ++j)
2484 {
2485 assert( 0 <= xoridx[j] && xoridx[j] < nvarsmat );
2486 xorbackidx[xoridx[j]] = j;
2487 }
2488
2489 /* init matrix and rhs */
2492 for (i = 0; i < nconss; ++i)
2493 {
2494 if ( ! xoractive[i] )
2495 continue;
2496
2497 assert( conss[i] != NULL );
2498 consdata = SCIPconsGetData(conss[i]);
2499 assert( consdata != NULL );
2500 assert( consdata->nvars > 0 );
2501
2502 SCIP_CALL( SCIPallocBufferArray(scip, &(A[nconssmat]), nvarsmat) ); /*lint !e866*/
2503 BMSclearMemoryArray(A[nconssmat], nvarsmat); /*lint !e866*/
2504
2505 /* correct rhs w.r.t. to fixed variables and count nonfixed variables in constraint */
2506 b[nconssmat] = (Type) consdata->rhs;
2507 for (j = 0; j < consdata->nvars; ++j)
2508 {
2509 SCIP_VAR* var;
2510 int idx;
2511
2512 var = consdata->vars[j];
2513 assert( var != NULL );
2514
2515 /* replace negated variables */
2516 if ( SCIPvarIsNegated(var) )
2517 {
2519 assert( var != NULL );
2520 b[nconssmat] = ! b[nconssmat];
2521 }
2522
2523 /* replace aggregated variables */
2525 {
2526 SCIP_Real scalar;
2527 SCIP_Real constant;
2528
2529 scalar = SCIPvarGetAggrScalar(var);
2530 constant = SCIPvarGetAggrConstant(var);
2531
2532 /* the variable resolves to a constant, we just update the rhs */
2533 if( SCIPisEQ(scip, scalar, 0.0) )
2534 {
2535 assert(SCIPisEQ(scip, constant, 0.0) || SCIPisEQ(scip, constant, 1.0));
2536 if( SCIPisEQ(scip, constant, 1.0) )
2537 b[nconssmat] = ! b[nconssmat];
2538 var = NULL;
2539 break;
2540 }
2541 /* replace aggregated variable by active variable and update rhs, if needed */
2542 else
2543 {
2544 assert(SCIPisEQ(scip, scalar, 1.0) || SCIPisEQ(scip, scalar, -1.0));
2545 if( SCIPisEQ(scip, constant, 1.0) )
2546 b[nconssmat] = ! b[nconssmat];
2547
2549 assert(var != NULL);
2550 }
2551 }
2552 /* variable resolved to a constant */
2553 if( var == NULL )
2554 continue;
2555
2556 /* If the constraint contains multiaggregated variables, the solution might not be valid, since the
2557 * implications are not represented in the matrix.
2558 */
2560 noaggr = FALSE;
2561
2562 if ( SCIPcomputeVarLbLocal(scip, var) > 0.5 )
2563 {
2564 /* variable is fixed to 1, invert rhs */
2565 b[nconssmat] = ! b[nconssmat];
2566 assert( ! SCIPhashmapExists(varhash, var) );
2567 }
2568 else
2569 {
2573 {
2574 assert( SCIPhashmapExists(varhash, var) );
2575 idx = SCIPhashmapGetImageInt(varhash, var);
2576 assert( idx < nvarsmat );
2577 assert( 0 <= xorbackidx[idx] && xorbackidx[idx] < nvarsmat );
2578 A[nconssmat][xorbackidx[idx]] = 1;
2579 }
2580 }
2581 }
2582 ++nconssmat;
2583 }
2584 SCIPdebugMsg(scip, "Found %d non-fixed variables in %d nonempty xor constraints.\n", nvarsmat, nconssmat);
2586
2587 /* perform Gauss algorithm */
2590
2591#ifdef SCIP_OUTPUT
2592 SCIPinfoMessage(scip, NULL, "Matrix before Gauss (size: %d x %d):\n", nconssmat, nvarsmat);
2593 for (i = 0; i < nconssmat; ++i)
2594 {
2595 for (j = 0; j < nvarsmat; ++j)
2596 SCIPinfoMessage(scip, NULL, "%d ", A[i][j]);
2597 SCIPinfoMessage(scip, NULL, " = %d\n", b[i]);
2598 }
2599 SCIPinfoMessage(scip, NULL, "\n");
2600#endif
2601
2602 rank = -1;
2603 if ( ! SCIPisStopped(scip) )
2604 {
2605 rank = computeRowEchelonGF2(scip, nconssmat, nvarsmat, p, s, A, b);
2606 assert( rank <= nconssmat && rank <= nvarsmat );
2607 }
2608
2609 /* rank is < 0 if the solution process has been stopped */
2610 if ( rank >= 0 )
2611 {
2612#ifdef SCIP_OUTPUT
2613 SCIPinfoMessage(scip, NULL, "Matrix after Gauss (rank: %d):\n", rank);
2614 for (i = 0; i < nconssmat; ++i)
2615 {
2616 for (j = 0; j < nvarsmat; ++j)
2617 SCIPinfoMessage(scip, NULL, "%d ", A[p[i]][j]);
2618 SCIPinfoMessage(scip, NULL, " = %d\n", b[p[i]]);
2619 }
2620 SCIPinfoMessage(scip, NULL, "\n");
2621#endif
2622
2623 /* check whether system is feasible */
2624 for (i = rank; i < nconssmat; ++i)
2625 {
2626 if ( b[p[i]] != 0 )
2627 break;
2628 }
2629
2630 /* did not find nonzero entry in b -> equation system is feasible */
2631 if ( i >= nconssmat )
2632 {
2633 SCIPdebugMsg(scip, "System feasible with rank %d (nconss=%d)\n", rank, nconssmat);
2634
2635 /* matrix has full rank, solution is unique */
2636 if( rank == nvarsmat && noaggr )
2637 {
2638 SCIP_Bool tightened;
2639 SCIP_Bool infeasible;
2640 Type* x;
2641
2642 SCIPdebugMsg(scip, "Found unique solution.\n");
2643
2644 /* construct solution */
2646 solveRowEchelonGF2(nconssmat, nvarsmat, rank, p, s, A, b, x);
2647
2648#ifdef SCIP_OUTPUT
2649 SCIPinfoMessage(scip, NULL, "Solution:\n");
2650 for (j = 0; j < nvarsmat; ++j)
2651 SCIPinfoMessage(scip, NULL, "%d ", x[j]);
2652 SCIPinfoMessage(scip, NULL, "\n");
2653#endif
2654
2655 /* fix variables according to computed unique solution */
2656 for( j = 0; j < nvarsmat; ++j )
2657 {
2661 if( x[j] == 0 )
2662 {
2663 SCIP_CALL( SCIPtightenVarUb(scip, xorvars[j], 0.0, FALSE, &infeasible, &tightened) );
2664 assert(tightened);
2665 assert(!infeasible);
2666 }
2667 else
2668 {
2669 assert(x[j] == 1);
2670 SCIP_CALL( SCIPtightenVarLb(scip, xorvars[j], 1.0, FALSE, &infeasible, &tightened) );
2671 assert(tightened);
2672 assert(!infeasible);
2673 }
2674 }
2676 }
2677 /* matrix does not have full rank, we add the solution, but cannot derive fixings */
2678 else
2679 {
2680 SCIP_HEUR* heurtrysol;
2681
2682 SCIPdebugMsg(scip, "Found solution.\n");
2683
2684 /* try solution */
2685 heurtrysol = SCIPfindHeur(scip, "trysol");
2686
2687 if ( heurtrysol != NULL )
2688 {
2689 SCIP_Bool success;
2690 SCIP_VAR** vars;
2691 SCIP_SOL* sol;
2692 Type* x;
2693
2694 /* construct solution */
2696 solveRowEchelonGF2(nconssmat, nvarsmat, rank, p, s, A, b, x);
2697
2698#ifdef SCIP_OUTPUT
2699 SCIPinfoMessage(scip, NULL, "Solution:\n");
2700 for (j = 0; j < nvarsmat; ++j)
2701 SCIPinfoMessage(scip, NULL, "%d ", x[j]);
2702 SCIPinfoMessage(scip, NULL, "\n");
2703#endif
2704
2705 /* create solution */
2706 SCIP_CALL( SCIPcreateSol(scip, &sol, heurtrysol) );
2707
2708 /* transfer solution */
2709 for (j = 0; j < nvarsmat; ++j)
2710 {
2711 if ( x[j] != 0 )
2712 {
2717 }
2718 }
2720
2721 /* add *all* variables fixed to 1 */
2723 for (j = 0; j < nvars; ++j)
2724 {
2725 if ( SCIPcomputeVarLbLocal(scip, vars[j]) > 0.5 )
2726 {
2727 SCIP_CALL( SCIPsetSolVal(scip, sol, vars[j], 1.0) );
2728 SCIPdebugMsg(scip, "Added fixed variable <%s>.\n", SCIPvarGetName(vars[j]));
2729 }
2730 }
2731
2732 /* correct integral variables if necessary */
2733 for (i = 0; i < nconss; ++i)
2734 {
2735 consdata = SCIPconsGetData(conss[i]);
2736 assert(consdata != NULL);
2737
2738 /* only try for active constraints and integral variable; hope for the best if they are not active */
2739 if ( xoractive[i] && consdata->intvar != NULL && SCIPvarIsActive(consdata->intvar) )
2740 {
2741 SCIP_Real val;
2742 int nones = 0;
2743
2744 for (j = 0; j < consdata->nvars; ++j)
2745 {
2746 if ( SCIPgetSolVal(scip, sol, consdata->vars[j]) > 0.5 )
2747 ++nones;
2748 }
2749 /* if there are aggregated variables, the solution might not be feasible */
2750 assert( ! noaggr || nones % 2 == (int) consdata->rhs );
2751 if ( (unsigned int) nones != consdata->rhs )
2752 {
2753 val = (SCIP_Real) (nones - (int) consdata->rhs)/2;
2754 if ( SCIPisGE(scip, val, SCIPvarGetLbGlobal(consdata->intvar)) && SCIPisLE(scip, val, SCIPvarGetUbGlobal(consdata->intvar)) )
2755 {
2756 SCIP_CALL( SCIPsetSolVal(scip, sol, consdata->intvar, val) );
2757 }
2758 }
2759 }
2760 }
2762
2763 /* check feasibility of new solution and pass it to trysol heuristic */
2765 if ( success )
2766 {
2767 SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, sol) );
2768 SCIPdebugMsg(scip, "Creating solution was successful.\n");
2769 }
2770#ifdef SCIP_DEBUG
2771 else
2772 {
2773 /* the solution might not be feasible, because of additional constraints */
2774 SCIPdebugMsg(scip, "Creating solution was not successful.\n");
2775 }
2776#endif
2778 }
2779 }
2780 }
2781 else
2782 {
2784 SCIPdebugMsg(scip, "System not feasible.\n");
2785 }
2786 }
2787
2788 /* free storage */
2791 j = nconssmat - 1;
2792 for (i = nconss - 1; i >= 0 ; --i)
2793 {
2794 consdata = SCIPconsGetData(conss[i]);
2795 assert(consdata != NULL);
2796
2797 if ( consdata->nvars == 0 )
2798 continue;
2799
2800 if( !xoractive[i] )
2801 continue;
2802
2803 SCIPfreeBufferArray(scip, &(A[j]));
2804 --j;
2805 }
2812 SCIPhashmapFree(&varhash);
2813
2814 return SCIP_OKAY;
2815}
2816
2817/** for each variable in the xor constraint, add it to conflict set; for integral variable add corresponding bound */
2818static
2820 SCIP* scip, /**< SCIP data structure */
2821 SCIP_CONS* cons, /**< constraint that inferred the bound change */
2822 SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2823 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
2824 PROPRULE proprule /**< propagation rule */
2825 )
2826{
2827 SCIP_CONSDATA* consdata;
2828 SCIP_VAR** vars;
2829 int nvars;
2830 int i;
2831
2832 assert( cons != NULL );
2833
2834 consdata = SCIPconsGetData(cons);
2835 assert(consdata != NULL);
2836 vars = consdata->vars;
2837 nvars = consdata->nvars;
2838
2839 switch( proprule )
2840 {
2841 case PROPRULE_0:
2842 assert( infervar == NULL || infervar == consdata->intvar );
2843
2844 /* the integral variable was fixed, because all variables were fixed */
2845 for (i = 0; i < nvars; ++i)
2846 {
2849 }
2850 break;
2851
2852 case PROPRULE_1:
2853 /* the variable was inferred, because all other variables were fixed */
2854 for (i = 0; i < nvars; ++i)
2855 {
2856 /* add variables that were fixed to 1 before */
2857 if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2858 {
2859 assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2861 }
2862 /* add variables that were fixed to 0 */
2863 else if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2864 {
2865 assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2867 }
2868 else
2869 {
2870 /* check changed variable (changed variable is 0 or 1 afterwards) */
2871 assert( vars[i] == infervar );
2872 }
2873 }
2874 break;
2875
2876 case PROPRULE_INTLB:
2877 assert( consdata->intvar != NULL );
2878
2879 if( infervar != consdata->intvar )
2880 {
2881 /* the variable was fixed, because of the lower bound of the integral variable */
2882 SCIP_CALL( SCIPaddConflictLb(scip, consdata->intvar, NULL) );
2883 }
2884 /* to many and the other fixed variables */
2885 for (i = 0; i < nvars; ++i)
2886 {
2887 /* add variables that were fixed to 0 */
2888 if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2889 {
2890 assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2892 }
2893 }
2894 break;
2895
2896 case PROPRULE_INTUB:
2897 assert( consdata->intvar != NULL );
2898
2899 if( infervar != consdata->intvar )
2900 {
2901 /* the variable was fixed, because of upper bound of the integral variable and the other fixed variables */
2902 SCIP_CALL( SCIPaddConflictUb(scip, consdata->intvar, NULL) );
2903 }
2904 for (i = 0; i < nvars; ++i)
2905 {
2906 /* add variables that were fixed to 1 */
2907 if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2908 {
2909 assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2911 }
2912 }
2913 break;
2914
2915 case PROPRULE_INVALID:
2916 default:
2917 SCIPerrorMessage("invalid inference information %d in xor constraint <%s>\n", proprule, SCIPconsGetName(cons));
2918 SCIPABORT();
2919 return SCIP_INVALIDDATA; /*lint !e527*/
2920 }
2921
2922 return SCIP_OKAY;
2923}
2924
2925/** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
2926static
2928 SCIP* scip, /**< SCIP data structure */
2929 SCIP_CONS* cons, /**< xor constraint that detected the conflict */
2930 SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2931 PROPRULE proprule /**< propagation rule */
2932 )
2933{
2934 /* conflict analysis can only be applied in solving stage and if it is applicable */
2936 return SCIP_OKAY;
2937
2938 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2940
2941 /* add bound changes */
2942 SCIP_CALL( addConflictBounds(scip, cons, infervar, NULL, proprule) );
2943
2944 /* analyze the conflict */
2946
2947 return SCIP_OKAY;
2948}
2949
2950/** propagates constraint with the following rules:
2951 * (0) all variables are fixed => can fix integral variable
2952 * (1) all except one variable fixed => fix remaining variable and integral variable
2953 * (2) depending on the amount of fixed binary variables we can tighten the integral variable
2954 * (3) depending on the lower bound of the integral variable one can fix variables to 1
2955 * (4) depending on the upper bound of the integral variable one can fix variables to 0
2956 */
2957static
2959 SCIP* scip, /**< SCIP data structure */
2960 SCIP_CONS* cons, /**< xor constraint to be processed */
2961 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2962 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2963 int* nfixedvars, /**< pointer to add up the number of fixed variables */
2964 int* nchgbds /**< pointer to add up the number of found domain reductions */
2965 )
2966{
2967 SCIP_CONSDATA* consdata;
2968 SCIP_VAR** vars;
2969 SCIP_Bool infeasible;
2970 SCIP_Bool tightened;
2971 SCIP_Bool odd;
2972 SCIP_Bool counted;
2973 int nvars;
2974 int nfixedones;
2975 int nfixedzeros;
2976 int watchedvar1;
2977 int watchedvar2;
2978 int i;
2979
2980 assert(scip != NULL);
2981 assert(cons != NULL);
2982 assert(eventhdlr != NULL);
2983 assert(cutoff != NULL);
2984 assert(nfixedvars != NULL);
2985 assert(nchgbds != NULL);
2986
2987 /* propagation can only be applied, if we know all operator variables */
2988 if( SCIPconsIsModifiable(cons) )
2989 return SCIP_OKAY;
2990
2991 consdata = SCIPconsGetData(cons);
2992 assert(consdata != NULL);
2993
2994 vars = consdata->vars;
2995 nvars = consdata->nvars;
2996
2997 /* don't process the constraint, if the watched variables weren't fixed to any value since last propagation call */
2998 if( consdata->propagated )
2999 return SCIP_OKAY;
3000
3001 /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
3003 {
3004 SCIP_CALL( SCIPincConsAge(scip, cons) );
3005 }
3006
3007 /* propagation cannot be applied, if we have at least two unfixed variables left;
3008 * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
3009 * if these ones get fixed
3010 */
3011 watchedvar1 = consdata->watchedvar1;
3012 watchedvar2 = consdata->watchedvar2;
3013
3014 /* check, if watched variables are still unfixed */
3015 if( watchedvar1 != -1 )
3016 {
3017 if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar1]) < 0.5 )
3018 watchedvar1 = -1;
3019 }
3020 if( watchedvar2 != -1 )
3021 {
3022 if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar2]) < 0.5 )
3023 watchedvar2 = -1;
3024 }
3025
3026 /* if only one watched variable is still unfixed, make it the first one */
3027 if( watchedvar1 == -1 )
3028 {
3029 watchedvar1 = watchedvar2;
3030 watchedvar2 = -1;
3031 }
3032 assert(watchedvar1 != -1 || watchedvar2 == -1);
3033
3034 /* if the watched variables are invalid (fixed), find new ones if existing; count the parity */
3035 odd = consdata->rhs;
3036 nfixedones = 0;
3037 nfixedzeros = 0;
3038 counted = FALSE;
3039 if( watchedvar2 == -1 )
3040 {
3041 for( i = 0; i < nvars; ++i )
3042 {
3043 if( SCIPvarGetLbLocal(vars[i]) > 0.5 )
3044 {
3045 odd = !odd;
3046 ++nfixedones;
3047 }
3048 else if( SCIPvarGetUbLocal(vars[i]) < 0.5 )
3049 ++nfixedzeros;
3050 else
3051 {
3052 assert(SCIPvarGetUbLocal(vars[i]) > 0.5);
3053 assert(SCIPvarGetLbLocal(vars[i]) < 0.5);
3054
3055 if( watchedvar1 == -1 )
3056 {
3057 assert(watchedvar2 == -1);
3058 watchedvar1 = i;
3059 }
3060 else if( watchedvar2 == -1 && watchedvar1 != i )
3061 {
3062 watchedvar2 = i;
3063 }
3064 }
3065 }
3066 counted = TRUE;
3067 }
3068 assert(watchedvar1 != -1 || watchedvar2 == -1);
3069
3070 /* if all variables are fixed, we can decide the feasibility of the constraint */
3071 if( watchedvar1 == -1 )
3072 {
3073 assert(watchedvar2 == -1);
3074 assert(counted);
3075
3076 if( odd )
3077 {
3078 SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is infeasible\n", SCIPconsGetName(cons));
3079
3080 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
3083
3084 *cutoff = TRUE;
3085 }
3086 else
3087 {
3088 /* fix integral variable if present */
3089 if ( consdata->intvar != NULL && !consdata->deleteintvar )
3090 {
3091 int fixval;
3092
3093 assert( ! *cutoff );
3094 assert( (nfixedones - (int) consdata->rhs) % 2 == 0 );
3095
3096 fixval = (nfixedones - (int) consdata->rhs)/2; /*lint !e713*/
3097
3098 SCIPdebugMsg(scip, "fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3099
3100 /* check whether value to fix is outside bounds */
3101 if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3102 {
3103 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3104 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3105 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3106
3109
3110 *cutoff = TRUE;
3111 }
3112 else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3113 {
3114 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3115 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3116 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3117
3120
3121 *cutoff = TRUE;
3122 }
3123 else if( SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3124 {
3125 if ( ! SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->intvar), (SCIP_Real) fixval) )
3126 {
3127 SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3128 assert( tightened );
3129 assert( ! infeasible );
3130 }
3131
3132 if ( ! SCIPisEQ(scip, SCIPvarGetUbLocal(consdata->intvar), (SCIP_Real) fixval) )
3133 {
3134 SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3135 assert( tightened );
3136 assert( ! infeasible );
3137 }
3138
3139 ++(*nfixedvars);
3140 }
3141 }
3142 else
3143 {
3144 SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is feasible\n", SCIPconsGetName(cons));
3145 }
3146 }
3148
3149 return SCIP_OKAY;
3150 }
3151
3152 /* if only one variable is not fixed, this variable can be deduced */
3153 if( watchedvar2 == -1 )
3154 {
3155 assert(watchedvar1 != -1);
3156 assert(counted);
3157
3158 SCIPdebugMsg(scip, "constraint <%s>: only one unfixed variable -> fix <%s> to %u\n",
3159 SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]), odd);
3160
3161 SCIP_CALL( SCIPinferBinvarCons(scip, vars[watchedvar1], odd, cons, (int)PROPRULE_1, &infeasible, &tightened) );
3162 assert(!infeasible);
3163 assert(tightened);
3164
3165 (*nfixedvars)++;
3166
3167 /* fix integral variable if present and not multi-aggregated */
3168 if ( consdata->intvar != NULL && !consdata->deleteintvar && SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3169 {
3170 int fixval;
3171
3172 /* if variable has been fixed to 1, adjust number of fixed variables */
3173 if ( odd )
3174 ++nfixedones;
3175
3176 assert( (nfixedones - (int) consdata->rhs) % 2 == 0 );
3177
3178 fixval = (nfixedones - (int) consdata->rhs)/2; /*lint !e713*/
3179 SCIPdebugMsg(scip, "should fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3180
3181 /* check whether value to fix is outside bounds */
3182 if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3183 {
3184 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3185 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3186 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3187
3190
3191 *cutoff = TRUE;
3192 }
3193 else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3194 {
3195 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3196 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3197 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3198
3201
3202 *cutoff = TRUE;
3203 }
3204 else
3205 {
3206 if( SCIPvarGetLbLocal(consdata->intvar) + 0.5 < (SCIP_Real) fixval )
3207 {
3208 SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3209 assert( tightened );
3210 assert( ! infeasible );
3211 }
3212
3213 if( SCIPvarGetUbLocal(consdata->intvar) - 0.5 > (SCIP_Real) fixval )
3214 {
3215 SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3216 assert( tightened );
3217 assert( ! infeasible );
3218 }
3219 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar)));
3220
3221 ++(*nfixedvars);
3222 }
3223 }
3224
3227
3228 return SCIP_OKAY;
3229 }
3230
3231 /* propagate w.r.t. integral variable */
3232 if ( consdata->intvar != NULL && !consdata->deleteintvar )
3233 {
3234 SCIP_Real newlb;
3235 SCIP_Real newub;
3236 int nonesmin;
3237 int nonesmax;
3238
3239 if( !counted )
3240 {
3241 assert(nfixedzeros == 0);
3242 assert(nfixedones == 0);
3243
3244 for( i = 0; i < nvars; ++i )
3245 {
3246 if( SCIPvarGetLbLocal(vars[i]) > 0.5 )
3247 ++nfixedones;
3248 else if( SCIPvarGetUbLocal(vars[i]) < 0.5 )
3249 ++nfixedzeros;
3250 }
3251 }
3252 assert( nfixedones + nfixedzeros < nvars );
3253
3254 assert( SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(consdata->intvar)) );
3255 assert( SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(consdata->intvar)) );
3256
3257 nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3258 nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3259
3260 /* the number of possible variables that can get value 1 is less than the minimum bound */
3261 if ( nvars - nfixedzeros < nonesmin )
3262 {
3263 SCIPdebugMsg(scip, "constraint <%s>: at most %d variables can take value 1, but there should be at least %d.\n", SCIPconsGetName(cons), nvars - nfixedones, nonesmin);
3264
3267
3268 *cutoff = TRUE;
3269
3270 return SCIP_OKAY;
3271 }
3272
3273 /* the number of variables that are fixed to 1 is larger than the maximum bound */
3274 if ( nfixedones > nonesmax )
3275 {
3276 SCIPdebugMsg(scip, "constraint <%s>: at least %d variables are fixed to 1, but there should be at most %d.\n", SCIPconsGetName(cons), nfixedones, nonesmax);
3277
3280
3281 *cutoff = TRUE;
3282
3283 return SCIP_OKAY;
3284 }
3285
3286 if( SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3287 {
3288 /* compute new bounds on the integral variable */
3289 newlb = (SCIP_Real)((nfixedones + 1 - (int) consdata->rhs) / 2); /*lint !e653*/
3290 newub = (SCIP_Real)((nvars - nfixedzeros - (int) consdata->rhs) / 2); /*lint !e653*/
3291
3292 /* new lower bound is better */
3293 if( newlb > SCIPvarGetLbLocal(consdata->intvar) + 0.5 )
3294 {
3295 SCIPdebugMsg(scip, "constraint <%s>: propagated lower bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newlb);
3296 SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, newlb, cons, (int)PROPRULE_INTUB, TRUE, &infeasible, &tightened) );
3297 assert(tightened);
3298 assert(!infeasible);
3299
3300 ++(*nchgbds);
3301
3302 nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3303 }
3304
3305 /* new upper bound is better */
3306 if( newub < SCIPvarGetUbLocal(consdata->intvar) - 0.5 )
3307 {
3308 SCIPdebugMsg(scip, "constraint <%s>: propagated upper bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newub);
3309 SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, newub, cons, (int)PROPRULE_INTLB, TRUE, &infeasible, &tightened) );
3310 assert(tightened);
3311 assert(!infeasible);
3312
3313 ++(*nchgbds);
3314
3315 nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3316 }
3317
3318 assert(nvars - nfixedzeros >= nonesmin);
3319 assert(nfixedones <= nonesmax);
3320
3321 /* the number of variables that are free or fixed to 1 is exactly the minimum required -> fix free variables to 1 */
3322 if ( nvars - nfixedzeros == nonesmin )
3323 {
3324 SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 1 to reach lower bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmin);
3325
3326 for (i = 0; i < nvars; ++i)
3327 {
3328 if ( SCIPvarGetLbLocal(vars[i]) < 0.5 && SCIPvarGetUbLocal(vars[i]) > 0.5 )
3329 {
3330 SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], TRUE, cons, (int)PROPRULE_INTLB, &infeasible, &tightened) );
3331 assert( !infeasible );
3332 assert( tightened );
3333
3334 ++(*nfixedvars);
3335 }
3336 }
3339
3340 return SCIP_OKAY;
3341 }
3342
3343 /* the number of variables that are fixed to 1 is exactly the maximum required -> fix free variables to 0 */
3344 if ( nfixedones == nonesmax )
3345 {
3346 SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 0 to guarantee upper bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmax);
3347
3348 for (i = 0; i < nvars; ++i)
3349 {
3350 if ( SCIPvarGetLbLocal(vars[i]) < 0.5 && SCIPvarGetUbLocal(vars[i]) > 0.5 )
3351 {
3352 SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], FALSE, cons, (int)PROPRULE_INTUB, &infeasible, &tightened) );
3353 assert(!infeasible);
3354 assert(tightened);
3355 ++(*nfixedvars);
3356 }
3357 }
3360
3361 return SCIP_OKAY;
3362 }
3363 }
3364 }
3365
3366 /* switch to the new watched variables */
3367 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
3368
3369 /* mark the constraint propagated */
3370 consdata->propagated = TRUE;
3371
3372 return SCIP_OKAY;
3373}
3374
3375/** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
3376 * propagation rules (see propagateCons())
3377 */
3378static
3380 SCIP* scip, /**< SCIP data structure */
3381 SCIP_CONS* cons, /**< constraint that inferred the bound change */
3382 SCIP_VAR* infervar, /**< variable that was deduced */
3383 PROPRULE proprule, /**< propagation rule that deduced the value */
3384 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
3385 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3386 )
3387{
3388 assert(result != NULL);
3389
3390 SCIPdebugMsg(scip, "resolving fixations according to rule %d\n", (int) proprule);
3391
3392 SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, proprule) );
3394
3395 return SCIP_OKAY;
3396}
3397
3398/** try to use clique information to delete a part of the xor constraint or even fix variables */
3399static
3401 SCIP* scip, /**< SCIP data structure */
3402 SCIP_CONS* cons, /**< constraint that inferred the bound change */
3403 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3404 int* nchgcoefs, /**< pointer to add up the number of deleted entries */
3405 int* ndelconss, /**< pointer to add up the number of deleted constraints */
3406 int* naddconss, /**< pointer to add up the number of added constraints */
3407 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
3408 )
3409{
3410 SCIP_CONSDATA* consdata;
3411 SCIP_VAR** vars;
3412 int nvars;
3413 SCIP_Bool breaked;
3414 SCIP_Bool restart;
3415 int posnotinclq1;
3416 int posnotinclq2;
3417 int v;
3418 int v1;
3419
3420 assert(scip != NULL);
3421 assert(cons != NULL);
3422 assert(nfixedvars != NULL);
3423 assert(nchgcoefs != NULL);
3424 assert(ndelconss != NULL);
3425 assert(naddconss != NULL);
3426 assert(cutoff != NULL);
3427
3428 /* propagation can only be applied, if we know all operator variables */
3429 if( SCIPconsIsModifiable(cons) )
3430 return SCIP_OKAY;
3431
3432 consdata = SCIPconsGetData(cons);
3433 assert(consdata != NULL);
3434
3435 vars = consdata->vars;
3436 nvars = consdata->nvars;
3437
3438 if( nvars < 3 )
3439 return SCIP_OKAY;
3440
3441 /* we cannot perform this steps if the integer variables in not artificial */
3442 if( !consdata->deleteintvar )
3443 return SCIP_OKAY;
3444
3445#if 0 /* try to evaluate if clique presolving should only be done multiple times when the constraint changed */
3446 if( !consdata->changed )
3447 return SCIP_OKAY;
3448#endif
3449
3450 /* @todo: if clique information would have saved the type of the clique, like <= 1, or == 1 we could do more
3451 * presolving like:
3452 *
3453 * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2) == 1) => xor(x3,x4) = 0
3454 * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) == 1) => (x4 = 0 and delete xor constraint)
3455 */
3456
3457 /* 1. we have only clique information "<=", so we can check if all variables are in the same clique
3458 *
3459 * (xor(x1,x2,x3) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 = 1 and delete old
3460 * xor-constraint)
3461 *
3462 * (xor(x1,x2,x3) = 0 and clique(x1,x2,x3) <= 1) => (fix all variables x1 = x2 = x3 = 0 and delete old xor-
3463 * constraint)
3464 */
3465
3466 /* 2. we have only clique information "<=", so we can check if all but one variable are in the same clique
3467 *
3468 * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + x4 = 1 and
3469 * delete old xor constraint)
3470 *
3471 * (xor(x1,x2,x3,x4) = 0 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + ~x4 = 1 and
3472 * delete old xor constraint)
3473 */
3474
3475 posnotinclq1 = -1; /* index of variable that is possible not in the clique */
3476 posnotinclq2 = -1; /* index of variable that is possible not in the clique */
3477 breaked = FALSE;
3478 restart = FALSE;
3479
3480 v = nvars - 2;
3481 while( v >= 0 )
3482 {
3483 SCIP_VAR* var;
3484 SCIP_VAR* var1;
3485 SCIP_Bool value;
3486 SCIP_Bool value1;
3487
3489
3490 value = SCIPvarIsActive(vars[v]);
3491
3492 if( !value )
3494 else
3495 var = vars[v];
3496
3497 if( posnotinclq1 == v )
3498 {
3499 --v;
3500 continue;
3501 }
3502
3503 for( v1 = v+1; v1 < nvars; ++v1 )
3504 {
3505 if( posnotinclq1 == v1 )
3506 continue;
3507
3509
3510 if( !value1 )
3512 else
3513 var1 = vars[v1];
3514
3515 if( !SCIPvarsHaveCommonClique(var, value, var1, value1, TRUE) )
3516 {
3517 /* if the position of the variable which is not in the clique with all other variables is not yet
3518 * initialized, than do now, one of both variables does not fit
3519 */
3520 if( posnotinclq1 == -1 )
3521 {
3522 posnotinclq1 = v;
3523 posnotinclq2 = v1;
3524 }
3525 else
3526 {
3527 /* no clique with exactly nvars-1 variables */
3528 if( restart || (posnotinclq2 != v && posnotinclq2 != v1) )
3529 {
3530 breaked = TRUE;
3531 break;
3532 }
3533
3534 /* check the second variables for not fitting into the clique of (nvars - 1) variables */
3536 restart = TRUE;
3537 v = nvars - 1;
3538 }
3539
3540 break;
3541 }
3542 else
3543 assert(vars[v] != vars[v1]);
3544 }
3545
3546 if( breaked )
3547 break;
3548
3549 --v;
3550 }
3551
3552 /* at least nvars-1 variables are in one clique */
3553 if( !breaked ) /*lint !e774*/
3554 {
3555 /* all variables are in one clique, case 1 */
3556 if( posnotinclq1 == -1 )
3557 {
3558 /* all variables of xor constraints <%s> (with rhs == 1) are in one clique, so create a setpartitioning
3559 * constraint with all variables and delete this xor-constraint */
3560 if( consdata->rhs )
3561 {
3563 char consname[SCIP_MAXSTRLEN];
3564
3565 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_complete_clq", SCIPconsGetName(cons));
3571
3573 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3575 ++(*naddconss);
3576
3578 }
3579 /* all variables of xor constraints <%s> (with rhs == 0) are in one clique, so fixed all variables to 0 */
3580 else
3581 {
3582 SCIP_Bool infeasible;
3583 SCIP_Bool fixed;
3584
3585 SCIPdebugMsg(scip, "all variables of xor constraints <%s> are in one clique, so fixed all variables to 0\n",
3586 SCIPconsGetName(cons));
3588
3589 for( v = nvars - 1; v >= 0; --v )
3590 {
3591 SCIPdebugMsg(scip, "fixing variable <%s> to 0\n", SCIPvarGetName(vars[v]));
3592 SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, &infeasible, &fixed) );
3593
3594 assert(infeasible || fixed);
3595
3596 if( infeasible )
3597 {
3598 *cutoff = infeasible;
3599
3600 return SCIP_OKAY;
3601 }
3602 else
3603 ++(*nfixedvars);
3604 }
3605 }
3606 }
3607 /* all but one variable are in one clique, case 2 */
3608 else
3609 {
3611 char consname[SCIP_MAXSTRLEN];
3612
3613 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_completed_clq", SCIPconsGetName(cons));
3614
3615 /* complete clique by creating a set partioning constraint over all variables */
3616
3617 /* if rhs == FALSE we need to exchange the variable not appaering in the clique with the negated variables */
3618 if( !consdata->rhs )
3619 {
3625
3626 for( v = 0; v < nvars; ++v )
3627 {
3628 if( v == posnotinclq1 )
3629 {
3630 SCIP_VAR* var;
3631
3633 assert(var != NULL);
3634
3636 }
3637 else
3638 {
3640 }
3641 }
3642 }
3643 /* if rhs == TRUE we can add all variables to the clique constraint directly */
3644 else
3645 {
3651 }
3652
3654 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3656 ++(*naddconss);
3657
3659 }
3660
3661 /* fix integer variable if it exists */
3662 if( consdata->intvar != NULL )
3663 {
3664 SCIP_Bool infeasible;
3665 SCIP_Bool fixed;
3666
3667 SCIPdebugMsg(scip, "also fix the integer variable <%s> to 0\n", SCIPvarGetName(consdata->intvar));
3668 SCIP_CALL( SCIPfixVar(scip, consdata->intvar, 0.0, &infeasible, &fixed) );
3669
3670 assert(infeasible || fixed || SCIPvarGetStatus(consdata->intvar) == SCIP_VARSTATUS_FIXED);
3671
3672 if( infeasible )
3673 {
3674 *cutoff = infeasible;
3675 return SCIP_OKAY;
3676 }
3677 else if( fixed )
3678 ++(*nfixedvars);
3679 }
3680
3681 /* delete old redundant xor-constraint */
3682 SCIP_CALL( SCIPdelCons(scip, cons) );
3683 ++(*ndelconss);
3684 }
3685
3686 return SCIP_OKAY;
3687}
3688
3689/** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3690 * accordingly; in contrast to preprocessConstraintPairs(), it uses a hash table
3691 */
3692static
3694 SCIP* scip, /**< SCIP data structure */
3695 BMS_BLKMEM* blkmem, /**< block memory */
3696 SCIP_CONS** conss, /**< constraint set */
3697 int nconss, /**< number of constraints in constraint set */
3698 int* firstchange, /**< pointer to store first changed constraint */
3699 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
3700 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3701 int* naggrvars, /**< pointer to add up the number of aggregated variables */
3702 int* ndelconss, /**< pointer to count number of deleted constraints */
3703 int* naddconss, /**< pointer to count number of added constraints */
3704 SCIP_Bool* cutoff /**< pointer to store TRUE, if a cutoff was found */
3705 )
3706{
3707 SCIP_HASHTABLE* hashtable;
3708 int hashtablesize;
3709 int c;
3710
3711 assert(conss != NULL);
3712 assert(ndelconss != NULL);
3713
3714 /* create a hash table for the constraint set */
3715 hashtablesize = nconss;
3716 hashtablesize = MAX(hashtablesize, HASHSIZE_XORCONS);
3717
3718 SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3720
3721 /* check all constraints in the given set for redundancy */
3722 for( c = 0; c < nconss; ++c )
3723 {
3727 SCIP_CONSHDLR* conshdlr;
3728 SCIP_CONSHDLRDATA* conshdlrdata;
3729
3730 cons0 = conss[c];
3731
3733 continue;
3734
3735 /* get constraint handler data */
3736 conshdlr = SCIPconsGetHdlr(cons0);
3737 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3738 assert(conshdlrdata != NULL);
3739
3740 /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3741 * variables inside so we need to remove them for sorting
3742 */
3743 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3744 * merge multiple entries of the same or negated variables
3745 */
3746 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3747 if( *cutoff )
3748 goto TERMINATE;
3749
3751
3752 assert(consdata0 != NULL);
3753
3754 /* applyFixings() led to an empty or trivial constraint */
3755 if( consdata0->nvars <= 1 )
3756 {
3757 if( consdata0->nvars == 0 )
3758 {
3759 /* the constraints activity cannot match an odd right hand side */
3760 if( consdata0->rhs )
3761 {
3762 *cutoff = TRUE;
3763 break;
3764 }
3765 }
3766 else
3767 {
3768 /* exactly 1 variable left. */
3769 SCIP_Bool infeasible;
3770 SCIP_Bool fixed;
3771
3772 /* fix remaining variable */
3773 SCIP_CALL( SCIPfixVar(scip, consdata0->vars[0], (SCIP_Real) consdata0->rhs, &infeasible, &fixed) );
3774 assert(!infeasible);
3775
3776 if( fixed )
3777 ++(*nfixedvars);
3778 }
3779
3780 /* fix integral variable if present */
3781 if( consdata0->intvar != NULL && !consdata0->deleteintvar )
3782 {
3783 SCIP_Bool infeasible;
3784 SCIP_Bool fixed;
3785
3786 SCIP_CALL( SCIPfixVar(scip, consdata0->intvar, 0.0, &infeasible, &fixed) );
3787 assert(!infeasible);
3788
3789 if( fixed )
3790 ++(*nfixedvars);
3791 }
3792
3793 /* delete empty constraint */
3795 ++(*ndelconss);
3796
3797 continue;
3798 }
3799
3800 /* sort the constraint */
3802 assert(consdata0->sorted);
3803
3804 /* get constraint from current hash table with same variables as cons0 */
3805 cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3806
3807 if( cons1 != NULL )
3808 {
3810
3813
3815
3816 assert(consdata1 != NULL);
3817 assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3818
3819 assert(consdata0->sorted && consdata1->sorted);
3820 assert(consdata0->vars[0] == consdata1->vars[0]);
3821
3822 if( consdata0->rhs != consdata1->rhs )
3823 {
3824 *cutoff = TRUE;
3825 goto TERMINATE;
3826 }
3827
3828 /* aggregate parity variables into each other */
3829 if( consdata0->intvar != consdata1->intvar && consdata0->intvar != NULL )
3830 {
3831 if( consdata1->intvar != NULL )
3832 {
3833 SCIP_Bool redundant;
3834 SCIP_Bool aggregated;
3835 SCIP_Bool infeasible;
3836
3837 SCIP_CALL( SCIPaggregateVars(scip, consdata0->intvar, consdata1->intvar, 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
3838
3839 if( aggregated )
3840 {
3841 ++(*naggrvars);
3842 }
3843 if( infeasible )
3844 {
3845 *cutoff = TRUE;
3846 goto TERMINATE;
3847 }
3848 }
3849 /* the special case that only cons0 has a parity variable 'intvar' is treated by swapping cons0 and cons1 */
3850 else
3851 {
3852 SCIP_CALL( SCIPhashtableInsert(hashtable, (void *)cons0) );
3853 assert(SCIPhashtableRetrieve(hashtable, (void *)cons1) == cons0);
3854
3855 SCIPswapPointers((void**)&cons0, (void**)(&cons1));
3856 SCIPswapPointers((void**)&consdata0, (void**)(&consdata1));
3857 }
3858 }
3859
3860 /* delete cons0 and update flags of cons1 s.t. nonredundant information doesn't get lost */
3861 /* coverity[swapped_arguments] */
3864 (*ndelconss)++;
3865
3866 /* update the first changed constraint to begin the next aggregation round with */
3867 if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3869
3871 }
3872 else
3873 {
3874 /* no such constraint in current hash table: insert cons0 into hash table */
3875 SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3876 }
3877 }
3878
3879 TERMINATE:
3880 /* free hash table */
3881 SCIPhashtableFree(&hashtable);
3882
3883 return SCIP_OKAY;
3884}
3885
3886/** compares constraint with all prior constraints for possible redundancy or aggregation,
3887 * and removes or changes constraint accordingly
3888 */
3889static
3891 SCIP* scip, /**< SCIP data structure */
3892 SCIP_CONS** conss, /**< constraint set */
3893 int firstchange, /**< first constraint that changed since last pair preprocessing round */
3894 int chkind, /**< index of constraint to check against all prior indices upto startind */
3895 SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3896 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3897 int* naggrvars, /**< pointer to count number of aggregated variables */
3898 int* ndelconss, /**< pointer to count number of deleted constraints */
3899 int* naddconss, /**< pointer to count number of added constraints */
3900 int* nchgcoefs /**< pointer to add up the number of changed coefficients */
3901 )
3902{
3903 SCIP_CONSHDLR* conshdlr;
3904 SCIP_CONSHDLRDATA* conshdlrdata;
3907 SCIP_Bool cons0changed;
3908 int c;
3909
3910 assert(conss != NULL);
3912 assert(cutoff != NULL);
3913 assert(nfixedvars != NULL);
3914 assert(naggrvars != NULL);
3915 assert(ndelconss != NULL);
3916 assert(nchgcoefs != NULL);
3917
3918 /* get the constraint to be checked against all prior constraints */
3919 cons0 = conss[chkind];
3922
3924 assert(consdata0 != NULL);
3925 assert(consdata0->nvars >= 1);
3926
3927 /* get constraint handler data */
3928 conshdlr = SCIPconsGetHdlr(cons0);
3929 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3930 assert(conshdlrdata != NULL);
3931
3932 /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3933 * variables inside so we need to remove them for sorting
3934 */
3935 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3936 * merge multiple entries of the same or negated variables
3937 */
3938 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3939 if( *cutoff )
3940 return SCIP_OKAY;
3941
3942 /* sort cons0 */
3944 assert(consdata0->sorted);
3945
3946 /* check constraint against all prior constraints */
3947 cons0changed = consdata0->changed;
3948 consdata0->changed = FALSE;
3949 for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff) && SCIPconsIsActive(cons0) && !SCIPisStopped(scip); ++c )
3950 {
3955 SCIP_Bool parity;
3956 SCIP_Bool cons0hastwoothervars;
3957 SCIP_Bool cons1hastwoothervars;
3958 SCIP_Bool aborted;
3959 SCIP_Bool infeasible;
3960 SCIP_Bool fixed;
3961 SCIP_Bool redundant;
3962 SCIP_Bool aggregated;
3963 int v0;
3964 int v1;
3965
3966 cons1 = conss[c];
3967
3968 /* ignore inactive and modifiable constraints */
3970 continue;
3971
3973 assert(consdata1 != NULL);
3974
3975 if( !consdata1->deleteintvar )
3976 continue;
3977
3978 /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3979 * variables inside so we need to remove them for sorting
3980 */
3981 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3982 * merge multiple entries of the same or negated variables
3983 */
3984 SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3986 if( *cutoff )
3987 return SCIP_OKAY;
3988
3989 SCIPdebugMsg(scip, "preprocess xor constraint pair <%s>[chg:%u] and <%s>[chg:%u]\n",
3991
3992 /* if both constraints were not changed since last round, we can ignore the pair */
3993 if( !cons0changed && !consdata1->changed )
3994 continue;
3995
3996 /* applyFixings() led to an empty constraint */
3997 if( consdata1->nvars == 0 )
3998 {
3999 if( consdata1->rhs )
4000 {
4001 *cutoff = TRUE;
4002 break;
4003 }
4004 else
4005 {
4006 /* fix integral variable if present */
4007 if( consdata1->intvar != NULL && !consdata1->deleteintvar )
4008 {
4009 SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
4010 assert(!infeasible);
4011 if( fixed )
4012 ++(*nfixedvars);
4013 }
4014
4015 /* delete empty constraint */
4017 ++(*ndelconss);
4018
4019 continue;
4020 }
4021 }
4022 else if( consdata1->nvars == 1 )
4023 {
4024 /* fix remaining variable */
4025 SCIP_CALL( SCIPfixVar(scip, consdata1->vars[0], (SCIP_Real) consdata1->rhs, &infeasible, &fixed) );
4026 assert(!infeasible);
4027
4028 if( fixed )
4029 ++(*nfixedvars);
4030
4031 /* fix integral variable if present */
4032 if( consdata1->intvar != NULL && !consdata1->deleteintvar )
4033 {
4034 SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
4035 assert(!infeasible);
4036 if( fixed )
4037 ++(*nfixedvars);
4038 }
4039
4041 ++(*ndelconss);
4042
4043 /* check for fixed variable in cons0 and remove it */
4044 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4045 assert(!(*cutoff));
4046
4047 /* sort cons0 */
4049 assert(consdata0->sorted);
4050
4051 continue;
4052 }
4053 else if( consdata1->nvars == 2 )
4054 {
4055 if( !(consdata1->rhs) )
4056 {
4057 /* aggregate var0 == var1 */
4058 SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, -1.0, 0.0,
4059 &infeasible, &redundant, &aggregated) );
4060 }
4061 else
4062 {
4063 /* aggregate var0 == 1 - var1 */
4064 SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, 1.0, 1.0,
4065 &infeasible, &redundant, &aggregated) );
4066 }
4067 assert(!infeasible);
4068 assert(redundant || SCIPdoNotAggr(scip));
4069
4070 if( aggregated )
4071 {
4072 ++(*naggrvars);
4073
4074 /* check for aggregated variable in cons0 and remove it */
4075 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4076 if( *cutoff )
4077 return SCIP_OKAY;
4078
4079 /* sort cons0 */
4081 assert(consdata0->sorted);
4082 }
4083
4084 if( redundant )
4085 {
4086 /* fix or aggregate the intvar, if it exists */
4087 if( consdata1->intvar != NULL && !consdata1->deleteintvar )
4088 {
4089 /* we have var0 + var1 - 2 * intvar = 1, and aggregated var1 = 1 - var0,
4090 * thus, intvar is always 0 */
4091 if( consdata1->rhs )
4092 {
4093 SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
4094 assert(!infeasible);
4095 if( fixed )
4096 ++(*nfixedvars);
4097 }
4098 /* we have var0 + var1 - 2 * intvar = 0, and aggregated var1 = var0,
4099 * i.e., 2 * var0 - 2 * intvar = 0, so intvar = var0 holds and we aggregate */
4100 else
4101 {
4102 assert(!consdata1->rhs);
4103
4104 /* aggregate intvar == var0 */
4105 SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->intvar, 1.0, -1.0, 0.0,
4106 &infeasible, &redundant, &aggregated) );
4107 assert(!infeasible);
4108 assert(redundant || SCIPdoNotAggr(scip));
4109
4110 if( aggregated )
4111 {
4112 ++(*naggrvars);
4113 }
4114 }
4115 }
4116
4117 if( redundant )
4118 {
4120 ++(*ndelconss);
4121 }
4122 }
4123
4124 continue;
4125 }
4126 assert(consdata0->sorted);
4127
4128 /* sort cons1 */
4130 assert(consdata1->sorted);
4131
4132 /* check whether
4133 * (a) one problem variable set is a subset of the other, or
4134 * (b) the problem variable sets are almost equal with only one variable in each constraint that is not
4135 * member of the other
4136 */
4137 aborted = FALSE;
4138 parity = (consdata0->rhs ^ consdata1->rhs);
4141 singlevar0 = NULL;
4142 singlevar1 = NULL;
4143 v0 = 0;
4144 v1 = 0;
4146 {
4147 int cmp;
4148
4151
4152 if( v0 == consdata0->nvars )
4153 cmp = +1;
4154 else if( v1 == consdata1->nvars )
4155 cmp = -1;
4156 else
4158
4159 switch( cmp )
4160 {
4161 case -1:
4162 /* variable doesn't appear in cons1 */
4164 if( singlevar0 == NULL )
4165 {
4166 singlevar0 = consdata0->vars[v0];
4168 aborted = TRUE;
4169 }
4170 else
4171 {
4173 if( singlevar1 != NULL )
4174 aborted = TRUE;
4175 }
4176 v0++;
4177 break;
4178
4179 case +1:
4180 /* variable doesn't appear in cons0 */
4182 if( singlevar1 == NULL )
4183 {
4184 singlevar1 = consdata1->vars[v1];
4186 aborted = TRUE;
4187 }
4188 else
4189 {
4191 if( singlevar0 != NULL )
4192 aborted = TRUE;
4193 }
4194 v1++;
4195 break;
4196
4197 case 0:
4198 /* variable appears in both constraints */
4202 if( consdata0->vars[v0] != consdata1->vars[v1] )
4203 {
4205 parity = !parity;
4206 }
4207 v0++;
4208 v1++;
4209 break;
4210
4211 default:
4212 SCIPerrorMessage("invalid comparison result\n");
4213 SCIPABORT();
4214 return SCIP_INVALIDDATA; /*lint !e527*/
4215 }
4216 }
4217
4218 /* check if a useful presolving is possible */
4220 continue;
4221
4222 /* check if one problem variable set is a subset of the other */
4223 if( singlevar0 == NULL && singlevar1 == NULL )
4224 {
4225 /* both constraints are equal */
4226 if( !parity )
4227 {
4228 /* even parity: constraints are redundant */
4229 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are redundant: delete <%s>\n",
4233
4234 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4237 (*ndelconss)++;
4238
4239 if( consdata1->intvar != NULL )
4240 {
4241 /* need to update integer variable, consider the following case:
4242 * c1: xor(x1, x2, x3) = 1 (intvar1 = y1)
4243 * c2: xor(x1, x2, x3) = 1 (intvar0 = NULL or intvar0 = y0)
4244 *
4245 * if intvar0 = NULL we have to assign intvar0 = y1. otherwise, we have to ensure that y1 = y0 holds.
4246 * if aggregation is allowed, we can aggregate both variables. otherwise, we have to add a linear
4247 * constraint y1 - y0 = 0.
4248 */
4249 if( consdata0->intvar == NULL )
4250 {
4251 SCIP_CALL( setIntvar(scip, cons0, consdata1->intvar) );
4252 }
4253 else
4254 {
4255 /* aggregate integer variables */
4256 SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4257 &infeasible, &redundant, &aggregated) );
4258
4259 *cutoff = *cutoff || infeasible;
4260
4261 if( aggregated )
4262 {
4263 (*naggrvars)++;
4265 }
4266 else
4267 {
4269 char consname[SCIP_MAXSTRLEN];
4270 SCIP_VAR* newvars[2];
4271 SCIP_Real vals[2];
4272
4273 newvars[0] = consdata1->intvar;
4274 vals[0] = 1.0;
4275 newvars[1] = consdata0->intvar;
4276 vals[1] = -1.0;
4277
4278 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons1));
4279
4280 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, newvars, vals, 0.0, 0.0,
4281 SCIPconsIsInitial(cons1), SCIPconsIsSeparated(cons1), TRUE, /*SCIPconsIsEnforced(cons),*/
4282 TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
4285
4288 ++(*naddconss);
4289 }
4290 }
4291 }
4292 }
4293 else
4294 {
4295 /* odd parity: constraints are contradicting */
4296 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are contradicting\n",
4300 *cutoff = TRUE;
4301 }
4302 }
4303 else if( singlevar1 == NULL )
4304 {
4305 /* cons1 is a subset of cons0 */
4307 {
4308 /* only one additional variable in cons0: fix this variable according to the parity */
4309 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4313 SCIP_CALL( SCIPfixVar(scip, singlevar0, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4314 *cutoff = *cutoff || infeasible;
4315 if ( fixed )
4316 (*nfixedvars)++;
4317
4318 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4321 (*ndelconss)++;
4322 }
4323 else
4324 {
4325 int v;
4326
4327 /* more than one additional variable in cons0: add cons1 to cons0, thus eliminating the equal variables */
4328 SCIPdebugMsg(scip, "xor constraint <%s> is superset of <%s> with parity %u\n",
4332 for( v = 0; v < consdata1->nvars; ++v )
4333 {
4334 SCIP_CALL( addCoef(scip, cons0, consdata1->vars[v]) );
4335 }
4336
4337 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4339 assert(consdata0->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4340 }
4341
4342 if( *cutoff )
4343 return SCIP_OKAY;
4344
4346 assert(consdata0->sorted);
4347 }
4348 else if( singlevar0 == NULL )
4349 {
4350 /* cons0 is a subset of cons1 */
4352 {
4353 /* only one additional variable in cons1: fix this variable according to the parity */
4354 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4358 SCIP_CALL( SCIPfixVar(scip, singlevar1, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4359 assert(infeasible || fixed);
4360 *cutoff = *cutoff || infeasible;
4361 (*nfixedvars)++;
4362
4363 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4366 (*ndelconss)++;
4367 }
4368 else
4369 {
4370 int v;
4371
4372 /* more than one additional variable in cons1: add cons0 to cons1, thus eliminating the equal variables */
4373 SCIPdebugMsg(scip, "xor constraint <%s> is subset of <%s> with parity %u\n",
4377 for( v = 0; v < consdata0->nvars; ++v )
4378 {
4379 SCIP_CALL( addCoef(scip, cons1, consdata0->vars[v]) );
4380 }
4381 SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4383 assert(consdata1->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4384
4385 if( *cutoff )
4386 return SCIP_OKAY;
4387
4389 assert(consdata1->sorted);
4390 }
4391 }
4392 else
4393 {
4396
4397 /* sum of constraints is parity == singlevar0 xor singlevar1: aggregate variables and delete cons1 */
4398 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == xor(<%s>,<%s>)\n",
4401 if( !parity )
4402 {
4403 /* aggregate singlevar0 == singlevar1 */
4405 &infeasible, &redundant, &aggregated) );
4406 }
4407 else
4408 {
4409 /* aggregate singlevar0 == 1-singlevar1 */
4411 &infeasible, &redundant, &aggregated) );
4412 }
4413 assert(infeasible || redundant || SCIPdoNotAggr(scip));
4414
4415 *cutoff = *cutoff || infeasible;
4416 if( aggregated )
4417 (*naggrvars)++;
4418
4419 if( redundant )
4420 {
4421 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4424 (*ndelconss)++;
4425
4426 if( consdata1->intvar != NULL )
4427 {
4428 if( consdata0->intvar == NULL )
4429 {
4430 SCIP_CALL( setIntvar(scip, cons0, consdata0->intvar) );
4431 }
4432 else
4433 {
4434 /* aggregate integer variables */
4435 SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4436 &infeasible, &redundant, &aggregated) );
4437
4438 *cutoff = *cutoff || infeasible;
4439 if( aggregated )
4440 (*naggrvars)++;
4441 }
4442 }
4443 }
4444
4445 if( !consdata0->sorted )
4447 assert(consdata0->sorted);
4448
4449#if 0
4450 /* if aggregation in the core of SCIP is not changed we do not need to call applyFixing, this would be the correct
4451 * way
4452 */
4453 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
4454 * merge multiple entries of the same or negated variables
4455 */
4456 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4457
4458 if( *cutoff )
4459 return SCIP_OKAY;
4460#endif
4461 }
4462 }
4463
4464 return SCIP_OKAY;
4465}
4466
4467/** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs with a given artificial integer variable for the
4468 * linear relaxation
4469 *
4470 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
4471 */
4472static
4474 SCIP* scip, /**< SCIP data structure */
4475 SCIP_CONS** cons, /**< pointer to hold the created constraint */
4476 const char* name, /**< name of constraint */
4477 SCIP_Bool rhs, /**< right hand side of the constraint */
4478 int nvars, /**< number of operator variables in the constraint */
4479 SCIP_VAR** vars, /**< array with operator variables of constraint */
4480 SCIP_VAR* intvar, /**< artificial integer variable for linear relaxation */
4481 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4482 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4483 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4484 * Usually set to TRUE. */
4485 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4486 * TRUE for model constraints, FALSE for additional, redundant constraints. */
4487 SCIP_Bool check, /**< should the constraint be checked for feasibility?
4488 * TRUE for model constraints, FALSE for additional, redundant constraints. */
4489 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4490 * Usually set to TRUE. */
4491 SCIP_Bool local, /**< is constraint only valid locally?
4492 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4493 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4494 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4495 * adds coefficients to this constraint. */
4496 SCIP_Bool dynamic, /**< is constraint subject to aging?
4497 * Usually set to FALSE. Set to TRUE for own cuts which
4498 * are separated as constraints. */
4499 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4500 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4501 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4502 * if it may be moved to a more global node?
4503 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4504 )
4505{
4506 SCIP_CONSHDLR* conshdlr;
4507 SCIP_CONSDATA* consdata;
4508
4509 /* find the xor constraint handler */
4510 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
4511 if( conshdlr == NULL )
4512 {
4513 SCIPerrorMessage("xor constraint handler not found\n");
4514 return SCIP_PLUGINNOTFOUND;
4515 }
4516
4517 /* create constraint data */
4518 SCIP_CALL( consdataCreate(scip, &consdata, rhs, nvars, vars, intvar) );
4519
4520 /* create constraint */
4521 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
4522 local, modifiable, dynamic, removable, stickingatnode) );
4523
4524 return SCIP_OKAY;
4525}
4526
4527
4528
4529/*
4530 * Linear constraint upgrading
4531 */
4532
4533/** tries to upgrade a linear constraint into an xor constraint
4534 *
4535 * Assuming all variables are binary and have coefficients with an absolute value 1, except for an integer (or binary) variable
4536 * \f$z\f$ which has coefficient \f$a \in \{-2,2\}\f$ with absolute value 2 and appears only in this constraint,
4537 * we can transform:
4538 * \f[
4539 * \begin{array}{ll}
4540 * & -\sum_{i \in I} x_i + \sum_{j \in J} x_j + a \cdot z = r \\
4541 * \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j + a \cdot z = r + |I| \\
4542 * \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j - 2 \cdot y = (r + |I|) \text{ mod } 2,
4543 * \end{array}
4544 * \f]
4545 * where
4546 * \f[
4547 * y = \begin{cases}
4548 * \left\lfloor \frac{r + |I|}{2} \right\rfloor + z & \text{if }a = -2\\
4549 * \left\lfloor \frac{r + |I|}{2} \right\rfloor - z & \text{if }a = 2.
4550 * \end{cases}
4551 * \f]
4552 * If \f$a = -2\f$ and \f$z \in [\ell_z, u_z]\f$, then \f$y \in [\ell_y, u_y]\f$, where \f$\ell_y = \left\lfloor
4553 * \frac{r + |I|}{2} \right\rfloor + \ell_z\f$ and \f$u_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor + u_z\f$.
4554 *
4555 * If \f$a = 2\f$, then \f$\ell_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor - u_z\f$ and \f$u_y = \left\lfloor
4556 * \frac{r + |I|}{2} \right\rfloor - \ell_z\f$.
4557 *
4558 * Then consider the resulting XOR-constraint
4559 * \f[
4560 * \bigoplus_{i \in I} \bar{x}_i \oplus \bigoplus_{j \in j} x_j = (r + |I|) \text{ mod } 2.
4561 * \f]
4562 * If \f$\ell_y \leq 0\f$ and \f$u_y \geq (|I| + |J|)/2\f$, then the XOR constraint is a reformulation of the above
4563 * transformed constraint, otherwise it is a relaxation because the bounds on the \f$y\f$-variable may disallow
4564 * too many (or too few) operators set to 1. Therefore, the XOR constraint handler verifies in this case that the linear
4565 * equation holds, ie., that the \f$y\f$-variable has the correct value.
4566 */
4567static
4569{ /*lint --e{715}*/
4570 assert( upgdcons != NULL );
4571 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 );
4572 assert( ! SCIPconsIsModifiable(cons) );
4573
4574 /* check, if linear constraint can be upgraded to xor constraint */
4575 /* @todo also applicable if the integer variable has a coefficient different from 2, e.g. a coefficient like 0.5 then
4576 * we could generate a new integer variable aggregated to the old one, possibly the constraint was then
4577 * normalized and all binary variables have coefficients of 2.0, if the coefficient is 4 then we need holes ...
4578 */
4579 if( integral && nposcont + nnegcont == 0 && nposbin + nnegbin + nposimplbin + nnegimplbin >= nvars-1 && ncoeffspone + ncoeffsnone == nvars-1 && ncoeffspint + ncoeffsnint == 1 )
4580 {
4582
4583 if ( SCIPisEQ(scip, lhs, rhs) && SCIPisIntegral(scip, lhs) )
4584 {
4585 SCIP_VAR** xorvars;
4587 SCIP_Bool postwo = FALSE;
4588 int cnt = 0;
4589 int j;
4590
4592
4593 /* check parity of constraints */
4594 for( j = nvars - 1; j >= 0; --j )
4595 {
4596 if( SCIPisEQ(scip, REALABS(vals[j]), 2.0) )
4597 {
4598 parityvar = vars[j];
4599 postwo = (vals[j] > 0.0);
4600 }
4601 else if( !SCIPisEQ(scip, REALABS(vals[j]), 1.0) )
4602 break;
4603 else
4604 {
4605 /* exit if variable is not binary or implicit binary */
4606 if ( ! SCIPvarIsBinary(vars[j]) )
4607 {
4608 parityvar = NULL;
4609 break;
4610 }
4611
4612 /* need negated variables for correct propagation to the integer variable */
4613 if( vals[j] < 0.0 )
4614 {
4616 assert(xorvars[cnt] != NULL);
4617 }
4618 else
4619 xorvars[cnt] = vars[j];
4620 ++cnt;
4621 }
4622 }
4623
4624 if( parityvar != NULL )
4625 {
4626 assert(cnt == nvars - 1);
4627
4628 /* check whether parity variable is present only in this constraint */
4631 {
4632 SCIP_VAR* intvar;
4633 SCIP_Bool rhsparity;
4634 SCIP_Bool neednew;
4635 int intrhs;
4636
4637 /* adjust the side, since we negated all binary variables with -1.0 as a coefficient */
4638 rhs += ncoeffsnone;
4639
4640 intrhs = (int) SCIPfloor(scip, rhs);
4641 rhsparity = ((SCIP_Bool) (intrhs % 2)); /*lint !e571*/
4642
4643 /* we need a new variable if the rhs is not 0 or 1 or if the coefficient was +2, since in these cases, we
4644 * need to aggregate the variables (flipping signs and/or shifting */
4645 if ( (intrhs != 1 && intrhs != 0) || postwo )
4646 neednew = TRUE;
4647 else
4648 neednew = FALSE;
4649
4650 /* check if we can use the parity variable as integer variable of the XOR constraint or do we need to
4651 * create a new variable and aggregate */
4652 if( neednew )
4653 {
4654 char varname[SCIP_MAXSTRLEN];
4655 SCIP_Real lb;
4656 SCIP_Real ub;
4657 SCIP_Bool isbinary;
4658 SCIP_Bool infeasible;
4659 SCIP_Bool redundant;
4660 SCIP_Bool aggregated;
4661 int intrhshalfed;
4662
4663 intrhshalfed = intrhs / 2;
4664
4665 if( postwo )
4666 {
4669 }
4670 else
4671 {
4674 }
4675 assert(SCIPisFeasLE(scip, lb, ub));
4678
4679 /* adjust bounds to be more integral */
4680 lb = SCIPfeasFloor(scip, lb);
4681 ub = SCIPfeasFloor(scip, ub);
4682
4683 isbinary = (SCIPisZero(scip, lb) && SCIPisEQ(scip, ub, 1.0));
4684
4685 /* something is wrong if parity variable is already binary, but artificial variable is not */
4687 {
4689 return SCIP_OKAY;
4690 }
4691
4693 SCIP_CALL( SCIPcreateVar(scip, &intvar, varname, lb, ub, 0.0,
4696 SCIP_CALL( SCIPaddVar(scip, intvar) );
4697
4698 SCIPdebugMsg(scip, "created new variable for aggregation:");
4699 SCIPdebug( SCIPprintVar(scip, intvar, NULL) );
4700
4701 SCIP_CALL( SCIPaggregateVars(scip, parityvar, intvar, 1.0, postwo ? 1.0 : -1.0,
4702 (SCIP_Real) (postwo ? intrhshalfed : -intrhshalfed), &infeasible, &redundant, &aggregated) );
4703 assert(!infeasible);
4704
4705 /* maybe aggregation was forbidden, than we cannot upgrade this constraint */
4706 if( !aggregated )
4707 {
4709 return SCIP_OKAY;
4710 }
4711
4712 assert(redundant);
4713 assert(SCIPvarIsActive(intvar));
4714
4715#ifdef SCIP_DEBUG
4717 {
4718 SCIPdebugMsg(scip, "aggregated: <%s> = %g * <%s> + %g\n", SCIPvarGetName(parityvar),
4721 }
4722 else
4723 {
4725 SCIPdebugMsg(scip, "negated: <%s> = 1 - <%s>\n", SCIPvarGetName(parityvar),
4727 }
4728#endif
4729 }
4730 else
4731 intvar = parityvar;
4732
4733 assert(intvar != NULL);
4734
4740
4741 SCIPdebugMsg(scip, "upgraded constraint <%s> to XOR constraint:\n", SCIPconsGetName(cons));
4743
4744 if( neednew )
4745 {
4746 assert(intvar != parityvar);
4747 SCIP_CALL( SCIPreleaseVar(scip, &intvar) );
4748 }
4749 }
4750 }
4751
4753 }
4754 }
4755
4756 return SCIP_OKAY;
4757}
4758
4759
4760/*
4761 * Callback methods of constraint handler
4762 */
4763
4764/** copy method for constraint handler plugins (called when SCIP copies plugins) */
4765static
4767{ /*lint --e{715}*/
4768 assert(scip != NULL);
4769 assert(conshdlr != NULL);
4771
4772 /* call inclusion method of constraint handler */
4774
4775 *valid = TRUE;
4776
4777 return SCIP_OKAY;
4778}
4779
4780/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
4781static
4783{ /*lint --e{715}*/
4784 SCIP_CONSHDLRDATA* conshdlrdata;
4785
4786 /* free constraint handler data */
4787 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4788 assert(conshdlrdata != NULL);
4789
4790 conshdlrdataFree(scip, &conshdlrdata);
4791
4792 SCIPconshdlrSetData(conshdlr, NULL);
4793
4794 return SCIP_OKAY;
4795}
4796
4797/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4798static
4800{ /*lint --e{715}*/
4801 SCIP_CONSDATA* consdata;
4802 int c;
4803
4804 /* release and free the rows of all constraints */
4805 for( c = 0; c < nconss; ++c )
4806 {
4807 consdata = SCIPconsGetData(conss[c]);
4808 SCIP_CALL( consdataFreeRows(scip, consdata) );
4809 }
4810
4811 return SCIP_OKAY;
4812}
4813
4814
4815/** frees specific constraint data */
4816static
4818{ /*lint --e{715}*/
4819 SCIP_CONSHDLRDATA* conshdlrdata;
4820
4821 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4822 assert(conshdlrdata != NULL);
4823
4825 {
4826 int v;
4827
4828 for( v = (*consdata)->nvars - 1; v >= 0; --v )
4829 {
4830 SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4831 (SCIP_EVENTDATA*)(*consdata), -1) );
4832 }
4833 }
4834
4835 SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4836
4837 return SCIP_OKAY;
4838}
4839
4840
4841/** transforms constraint data into data belonging to the transformed problem */
4842static
4865
4866
4867/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4868static
4870{ /*lint --e{715}*/
4871 int i;
4872
4873 assert(infeasible != NULL);
4874
4875 *infeasible = FALSE;
4876
4877 for( i = 0; i < nconss && !(*infeasible); i++ )
4878 {
4879 assert(SCIPconsIsInitial(conss[i]));
4880 SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4881 }
4882
4883 return SCIP_OKAY;
4884}
4885
4886
4887/** separation method of constraint handler for LP solutions */
4888static
4890{ /*lint --e{715}*/
4891 SCIP_CONSHDLRDATA* conshdlrdata;
4892 SCIP_Bool separated;
4893 SCIP_Bool cutoff;
4894 int c;
4895
4897
4898 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4899 assert( conshdlrdata != NULL );
4900
4901 /* separate all useful constraints */
4902 for( c = 0; c < nusefulconss; ++c )
4903 {
4904 SCIP_CALL( separateCons(scip, conss[c], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
4905 if ( cutoff )
4907 else if ( separated )
4909 }
4910
4911 /* combine constraints to get more cuts */
4912 /**@todo combine constraints to get further cuts */
4913
4914 return SCIP_OKAY;
4915}
4916
4917
4918/** separation method of constraint handler for arbitrary primal solutions */
4919static
4921{ /*lint --e{715}*/
4922 SCIP_CONSHDLRDATA* conshdlrdata;
4923 SCIP_Bool separated;
4924 SCIP_Bool cutoff;
4925 int c;
4926
4928
4929 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4930 assert( conshdlrdata != NULL );
4931
4932 /* separate all useful constraints */
4933 for( c = 0; c < nusefulconss; ++c )
4934 {
4935 SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->separateparity, &separated, &cutoff) );
4936 if ( cutoff )
4938 else if ( separated )
4940 }
4941
4942 /* combine constraints to get more cuts */
4943 /**@todo combine constraints to get further cuts */
4944
4945 return SCIP_OKAY;
4946}
4947
4948
4949/** constraint enforcing method of constraint handler for LP solutions */
4950static
4952{ /*lint --e{715}*/
4953 SCIP_CONSHDLRDATA* conshdlrdata;
4954 SCIP_Bool violated;
4955 SCIP_Bool cutoff;
4956 int i;
4957
4958 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4959 assert( conshdlrdata != NULL );
4960
4961 /* method is called only for integral solutions, because the enforcing priority is negative */
4962 for( i = 0; i < nconss; i++ )
4963 {
4964 SCIP_CALL( checkCons(scip, conss[i], NULL, FALSE, &violated) );
4965 if( violated )
4966 {
4967 SCIP_Bool separated;
4968
4969 SCIP_CALL( separateCons(scip, conss[i], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
4970 if ( cutoff )
4972 else
4973 {
4974 assert(separated); /* because the solution is integral, the separation always finds a cut */
4976 }
4977 return SCIP_OKAY;
4978 }
4979 }
4981
4982 return SCIP_OKAY;
4983}
4984
4985
4986/** constraint enforcing method of constraint handler for relaxation solutions */
4987static
4989{ /*lint --e{715}*/
4990 SCIP_CONSHDLRDATA* conshdlrdata;
4991 SCIP_Bool violated;
4992 SCIP_Bool cutoff;
4993 int i;
4994
4995 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4996 assert( conshdlrdata != NULL );
4997
4998 /* method is called only for integral solutions, because the enforcing priority is negative */
4999 for( i = 0; i < nconss; i++ )
5000 {
5001 SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, &violated) );
5002 if( violated )
5003 {
5004 SCIP_Bool separated;
5005
5006 SCIP_CALL( separateCons(scip, conss[i], sol, conshdlrdata->separateparity, &separated, &cutoff) );
5007 if ( cutoff )
5009 else
5010 {
5011 assert(separated); /* because the solution is integral, the separation always finds a cut */
5013 }
5014 return SCIP_OKAY;
5015 }
5016 }
5018
5019 return SCIP_OKAY;
5020}
5021
5022
5023/** constraint enforcing method of constraint handler for pseudo solutions */
5024static
5026{ /*lint --e{715}*/
5027 SCIP_Bool violated;
5028 int i;
5029
5030 /* method is called only for integral solutions, because the enforcing priority is negative */
5031 for( i = 0; i < nconss; i++ )
5032 {
5033 SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, &violated) );
5034 if( violated )
5035 {
5037 return SCIP_OKAY;
5038 }
5039 }
5041
5042 return SCIP_OKAY;
5043}
5044
5045
5046/** feasibility check method of constraint handler for integral solutions */
5047static
5049{ /*lint --e{715}*/
5050 SCIP_Bool violated;
5051 int i;
5052
5054
5055 /* method is called only for integral solutions, because the enforcing priority is negative */
5056 for( i = 0; i < nconss && (*result == SCIP_FEASIBLE || completely); i++ )
5057 {
5058 SCIP_CALL( checkCons(scip, conss[i], sol, checklprows, &violated) );
5059 if( violated )
5060 {
5062
5063 if( printreason )
5064 {
5065 int v;
5066 int sum = 0;
5067 SCIP_CONSDATA* consdata;
5068
5069 consdata = SCIPconsGetData(conss[i]);
5070 assert( consdata != NULL );
5071
5072 SCIP_CALL( SCIPprintCons(scip, conss[i], NULL) );
5073
5074 for( v = 0; v < consdata->nvars; ++v )
5075 {
5076 if( SCIPgetSolVal(scip, sol, consdata->vars[v]) > 0.5 )
5077 sum++;
5078 }
5079
5080 if( consdata->intvar != NULL )
5081 {
5082 SCIPinfoMessage(scip, NULL, ";\nviolation: %d operands are set to TRUE but integer variable has value of %g\n", sum, SCIPgetSolVal(scip, sol, consdata->intvar));
5083 }
5084 else
5085 {
5086 SCIPinfoMessage(scip, NULL, ";\nviolation: %d operands are set to TRUE\n", sum );
5087 }
5088 }
5089 }
5090 }
5091
5092 return SCIP_OKAY;
5093}
5094
5095
5096/** domain propagation method of constraint handler */
5097static
5099{ /*lint --e{715}*/
5100 SCIP_CONSHDLRDATA* conshdlrdata;
5101 SCIP_Bool cutoff;
5102 int nfixedvars;
5103 int nchgbds;
5104 int c;
5105
5106 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5107 assert(conshdlrdata != NULL);
5108
5109 cutoff = FALSE;
5110 nfixedvars = 0;
5111 nchgbds = 0;
5112
5113 /* propagate all useful constraints */
5114 for( c = 0; c < nusefulconss && !cutoff; ++c )
5115 {
5116 SCIP_CALL( propagateCons(scip, conss[c], conshdlrdata->eventhdlr, &cutoff, &nfixedvars, &nchgbds) );
5117 }
5118
5119 /* return the correct result */
5120 if( cutoff )
5122 else if( nfixedvars > 0 || nchgbds > 0 )
5124 else
5125 {
5127 if ( ! SCIPinProbing(scip) )
5128 {
5129 int depth;
5130 int freq;
5131
5133 freq = conshdlrdata->gausspropfreq;
5134 if ( (depth == 0 && freq == 0) || (freq > 0 && depth % freq == 0) )
5135 {
5136 /* take useful constraints only - might improve success rate to take all */
5138 }
5139 }
5140 }
5141
5142 return SCIP_OKAY;
5143}
5144
5145/** presolving initialization method of constraint handler (called when presolving is about to begin) */
5146static
5148{ /*lint --e{715}*/
5149 SCIP_CONSHDLRDATA* conshdlrdata;
5150 SCIP_CONSDATA* consdata;
5151 int c;
5152 int v;
5153
5154 assert(conshdlr != NULL);
5155 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5156 assert(conshdlrdata != NULL);
5157
5158 /* catch all variable event for deleted variables, which is only used in presolving */
5159 for( c = nconss - 1; c >= 0; --c )
5160 {
5161 consdata = SCIPconsGetData(conss[c]);
5162 assert(consdata != NULL);
5163
5164 for( v = consdata->nvars - 1; v >= 0; --v )
5165 {
5166 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
5167 (SCIP_EVENTDATA*)consdata, NULL) );
5168 }
5169 }
5170
5171 return SCIP_OKAY;
5172}
5173
5174/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
5175static
5177{ /*lint --e{715}*/
5178 SCIP_CONSHDLRDATA* conshdlrdata;
5179 SCIP_CONSDATA* consdata;
5180 int c;
5181 int v;
5182
5183 assert(conshdlr != NULL);
5184 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5185 assert(conshdlrdata != NULL);
5186
5187 /* drop all variable event for deleted variables, which was only used in presolving */
5188 for( c = 0; c < nconss; ++c )
5189 {
5190 consdata = SCIPconsGetData(conss[c]);
5191 assert(consdata != NULL);
5192
5193 if( !SCIPconsIsDeleted(conss[c]) )
5194 {
5195 for( v = 0; v < consdata->nvars; ++v )
5196 {
5197 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
5198 (SCIP_EVENTDATA*)consdata, -1) );
5199 }
5200 }
5201 }
5202
5203 return SCIP_OKAY;
5204}
5205
5206/** presolving method of constraint handler */
5207static
5209{ /*lint --e{715}*/
5210 SCIP_CONSHDLRDATA* conshdlrdata;
5211 SCIP_CONS* cons;
5212 SCIP_CONSDATA* consdata;
5213 SCIP_Bool cutoff;
5214 SCIP_Bool redundant;
5215 SCIP_Bool aggregated;
5216 int oldnfixedvars;
5217 int oldnchgbds;
5218 int oldnaggrvars;
5219 int oldndelconss;
5220 int oldnchgcoefs;
5221 int firstchange;
5222 int c;
5223
5224 assert(result != NULL);
5225
5226 oldnfixedvars = *nfixedvars;
5227 oldnchgbds = *nchgbds;
5228 oldnaggrvars = *naggrvars;
5229 oldndelconss = *ndelconss;
5230 oldnchgcoefs = *nchgcoefs;
5231
5232 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5233 assert(conshdlrdata != NULL);
5234
5235 /* process constraints */
5236 cutoff = FALSE;
5238 for( c = 0; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
5239 {
5240 cons = conss[c];
5241 assert(cons != NULL);
5242 consdata = SCIPconsGetData(cons);
5243 assert(consdata != NULL);
5244
5245 /* force presolving the constraint in the initial round */
5246 if( nrounds == 0 )
5247 consdata->propagated = FALSE;
5248
5249 /* remember the first changed constraint to begin the next aggregation round with */
5250 if( firstchange == INT_MAX && consdata->changed )
5251 firstchange = c;
5252
5253 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
5254 * merge multiple entries of the same or negated variables
5255 */
5256 SCIP_CALL( applyFixings(scip, cons, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, &cutoff) );
5257
5258 if( cutoff )
5259 break;
5260
5261 /* propagate constraint */
5262 SCIP_CALL( propagateCons(scip, cons, conshdlrdata->eventhdlr, &cutoff, nfixedvars, nchgbds) );
5263
5264 if( !cutoff && !SCIPconsIsDeleted(cons) && !SCIPconsIsModifiable(cons) )
5265 {
5266 assert(consdata->nvars >= 2); /* otherwise, propagateCons() has deleted the constraint */
5267
5268 /* if only two variables are left, both have to be equal or opposite, depending on the rhs */
5269 if( consdata->nvars == 2 )
5270 {
5271 SCIPdebugMsg(scip, "xor constraint <%s> has only two unfixed variables, rhs=%u\n",
5272 SCIPconsGetName(cons), consdata->rhs);
5273
5274 assert(consdata->vars != NULL);
5275 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->vars[0]), 0.0));
5276 assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(consdata->vars[0]), 1.0));
5277 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->vars[1]), 0.0));
5278 assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(consdata->vars[1]), 1.0));
5279
5280 if( !consdata->rhs )
5281 {
5282 /* aggregate variables: vars[0] - vars[1] == 0 */
5283 SCIPdebugMsg(scip, " -> aggregate <%s> == <%s>\n", SCIPvarGetName(consdata->vars[0]),
5284 SCIPvarGetName(consdata->vars[1]));
5285 SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, -1.0, 0.0,
5286 &cutoff, &redundant, &aggregated) );
5287 }
5288 else
5289 {
5290 /* aggregate variables: vars[0] + vars[1] == 1 */
5291 SCIPdebugMsg(scip, " -> aggregate <%s> == 1 - <%s>\n", SCIPvarGetName(consdata->vars[0]),
5292 SCIPvarGetName(consdata->vars[1]));
5293 SCIP_CALL( SCIPaggregateVars(scip, consdata->vars[0], consdata->vars[1], 1.0, 1.0, 1.0,
5294 &cutoff, &redundant, &aggregated) );
5295 }
5296 assert(redundant || SCIPdoNotAggr(scip));
5297
5298 if( aggregated )
5299 {
5300 assert(redundant);
5301 (*naggrvars)++;
5302 }
5303
5304 /* the constraint can be deleted if the intvar is fixed or NULL */
5305 if( redundant )
5306 {
5307 SCIP_Bool fixedintvar;
5308
5309 fixedintvar = consdata->intvar == NULL ? TRUE : SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->intvar), SCIPvarGetUbGlobal(consdata->intvar));
5310
5311 if( fixedintvar )
5312 {
5313 /* if the integer variable is an original variable, i.e.,
5314 * consdata->deleteintvar == FALSE then the following
5315 * must hold:
5316 *
5317 * if consdata->rhs == 1 then the integer variable needs
5318 * to be fixed to zero, otherwise the constraint is
5319 * infeasible,
5320 *
5321 * if consdata->rhs == 0 then the integer variable needs
5322 * to be aggregated to one of the binary variables
5323 */
5324 assert(consdata->deleteintvar || (consdata->rhs && SCIPvarGetLbGlobal(consdata->intvar) < 0.5));
5325
5326 /* delete constraint */
5327 SCIP_CALL( SCIPdelCons(scip, cons) );
5328 (*ndelconss)++;
5329 }
5330 }
5331 }
5332 else if( (presoltiming & SCIP_PRESOLTIMING_MEDIUM) != 0 )
5333 {
5334 /* try to use clique information to upgrade the constraint to a set-partitioning constraint or fix
5335 * variables
5336 */
5337 SCIP_CALL( cliquePresolve(scip, cons, nfixedvars, nchgcoefs, ndelconss, naddconss, &cutoff) );
5338 }
5339 }
5340 }
5341
5342 /* process pairs of constraints: check them for equal operands;
5343 * only apply this expensive procedure, if the single constraint preprocessing did not find any reductions
5344 */
5345 if( !cutoff && (presoltiming & SCIP_PRESOLTIMING_EXHAUSTIVE) != 0 && SCIPisPresolveFinished(scip) )
5346 {
5347 if( firstchange < nconss && conshdlrdata->presolusehashing )
5348 {
5349 /* detect redundant constraints; fast version with hash table instead of pairwise comparison */
5350 SCIP_CALL( detectRedundantConstraints(scip, SCIPblkmem(scip), conss, nconss, &firstchange, nchgcoefs,
5351 nfixedvars, naggrvars, ndelconss, naddconss, &cutoff) );
5352 }
5353 if( conshdlrdata->presolpairwise )
5354 {
5355 SCIP_Longint npaircomparisons;
5356 int lastndelconss;
5357 npaircomparisons = 0;
5358 lastndelconss = *ndelconss;
5359
5360 for( c = firstchange; c < nconss && !cutoff && !SCIPisStopped(scip); ++c )
5361 {
5362 if( SCIPconsIsActive(conss[c]) && !SCIPconsIsModifiable(conss[c]) )
5363 {
5364 npaircomparisons += (SCIPconsGetData(conss[c])->changed) ? (SCIP_Longint) c : ((SCIP_Longint) c - (SCIP_Longint) firstchange);
5365
5367 &cutoff, nfixedvars, naggrvars, ndelconss, naddconss, nchgcoefs) );
5368
5370 {
5371 if( ((SCIP_Real) (*ndelconss - lastndelconss)) / ((SCIP_Real) npaircomparisons) < MINGAINPERNMINCOMPARISONS )
5372 break;
5373 lastndelconss = *ndelconss;
5374 npaircomparisons = 0;
5375 }
5376 }
5377 }
5378 }
5379 }
5380
5381 /* return the correct result code */
5382 if( cutoff )
5384 else if( *nfixedvars > oldnfixedvars || *nchgbds > oldnchgbds || *naggrvars > oldnaggrvars
5385 || *ndelconss > oldndelconss || *nchgcoefs > oldnchgcoefs )
5387 else
5389
5390 /* add extended formulation at the end of presolving if required */
5391 if ( conshdlrdata->addextendedform && *result == SCIP_DIDNOTFIND && SCIPisPresolveFinished(scip) )
5392 {
5393 for (c = 0; c < nconss && ! SCIPisStopped(scip); ++c)
5394 {
5395 int naddedconss = 0;
5396
5397 cons = conss[c];
5398 assert(cons != NULL);
5399 consdata = SCIPconsGetData(cons);
5400 assert(consdata != NULL);
5401
5402 if ( consdata->extvars != NULL )
5403 break;
5404
5405 if ( conshdlrdata->addflowextended )
5406 {
5407 SCIP_CALL( addExtendedFlowFormulation(scip, cons, naggrvars, &naddedconss) );
5408 }
5409 else
5410 {
5411 SCIP_CALL( addExtendedAsymmetricFormulation(scip, cons, naggrvars, &naddedconss) );
5412 }
5413 (*naddconss) += naddedconss;
5414 }
5415 }
5416
5417 return SCIP_OKAY;
5418}
5419
5420
5421/** propagation conflict resolving method of constraint handler */
5422static
5424{ /*lint --e{715}*/
5425 SCIP_CALL( resolvePropagation(scip, cons, infervar, (PROPRULE)inferinfo, bdchgidx, result) );
5426
5427 return SCIP_OKAY;
5428}
5429
5430
5431/** variable rounding lock method of constraint handler */
5432static
5434{ /*lint --e{715}*/
5435 SCIP_CONSDATA* consdata;
5436 int i;
5437
5439
5440 consdata = SCIPconsGetData(cons);
5441 assert(consdata != NULL);
5442
5443 /* external variables */
5444 for( i = 0; i < consdata->nvars; ++i )
5445 {
5446 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
5447 }
5448
5449 /* internal variable */
5450 if( consdata->intvar != NULL )
5451 {
5452 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->intvar, locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
5453 }
5454
5455 return SCIP_OKAY;
5456}
5457
5458
5459/** constraint display method of constraint handler */
5460static
5462{ /*lint --e{715}*/
5463 assert( scip != NULL );
5464 assert( conshdlr != NULL );
5465 assert( cons != NULL );
5466
5468
5469 return SCIP_OKAY;
5470}
5471
5472/** constraint copying method of constraint handler */
5473static
5475{ /*lint --e{715}*/
5479 SCIP_VAR* intvar;
5481 const char* consname;
5482 int nvars;
5483 int v;
5484
5485 assert(scip != NULL);
5486 assert(sourcescip != NULL);
5488
5489 (*valid) = TRUE;
5490
5493
5494 /* get variables and coefficients of the source constraint */
5495 sourcevars = sourceconsdata->vars;
5496 nvars = sourceconsdata->nvars;
5497 intvar = sourceconsdata->intvar;
5499
5500 if( name != NULL )
5501 consname = name;
5502 else
5503 consname = SCIPconsGetName(sourcecons);
5504
5505 if( nvars == 0 )
5506 {
5507 if( intvar != NULL )
5508 {
5509 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, intvar, &targetintvar, varmap, consmap, global, valid) );
5510 assert(!(*valid) || targetintvar != NULL);
5511
5512 if( targetintvar != NULL )
5513 {
5514 SCIPdebugMsg(scip, "Copied integral variable <%s> (bounds: [%g,%g])\n", SCIPvarGetName(targetintvar),
5515 global ? SCIPvarGetLbGlobal(intvar) : SCIPvarGetLbLocal(intvar),
5516 global ? SCIPvarGetUbGlobal(intvar) : SCIPvarGetUbLocal(intvar));
5517 }
5518 }
5519
5520 if( *valid )
5521 {
5522 SCIP_CALL( createConsXorIntvar(scip, cons, consname, SCIPgetRhsXor(sourcescip, sourcecons), 0, NULL,
5523 targetintvar, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable,
5524 stickingatnode) );
5525 }
5526
5527 return SCIP_OKAY;
5528 }
5529
5530 /* duplicate variable array */
5532
5533 /* map variables of the source constraint to variables of the target SCIP */
5534 for( v = 0; v < nvars && *valid; ++v )
5535 {
5536 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) );
5537 assert(!(*valid) || targetvars[v] != NULL);
5538 }
5539
5540 /* map artificial relaxation variable of the source constraint to variable of the target SCIP */
5541 if( *valid && intvar != NULL )
5542 {
5543 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, intvar, &targetintvar, varmap, consmap, global, valid) );
5544 assert(!(*valid) || targetintvar != NULL);
5545
5546 SCIPdebugMsg(scip, "Copied integral variable <%s> (bounds: [%g,%g])\n", SCIPvarGetName(targetintvar),
5547 global ? SCIPvarGetLbGlobal(intvar) : SCIPvarGetLbLocal(intvar),
5548 global ? SCIPvarGetUbGlobal(intvar) : SCIPvarGetUbLocal(intvar));
5549 }
5550
5551 /* only create the target constraints, if all variables could be copied */
5552 if( *valid )
5553 {
5555 targetintvar, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable,
5556 stickingatnode) );
5557 }
5558
5559 /* free buffer array */
5561
5562 return SCIP_OKAY;
5563}
5564
5565
5566/** constraint parsing method of constraint handler */
5567static
5569{ /*lint --e{715}*/
5570 SCIP_VAR** vars;
5571 char* endptr;
5572 int requiredsize;
5573 int varssize;
5574 int nvars;
5575
5576 SCIPdebugMsg(scip, "parse <%s> as xor constraint\n", str);
5577
5578 varssize = 100;
5579 nvars = 0;
5580
5581 /* allocate buffer array for variables */
5582 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
5583
5584 /* parse string */
5586
5587 if( *success )
5588 {
5589 SCIP_Real rhs;
5590
5591 /* check if the size of the variable array was big enough */
5592 if( varssize < requiredsize )
5593 {
5594 /* reallocate memory */
5595 varssize = requiredsize;
5596 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
5597
5598 /* parse string again with the correct size of the variable array */
5600 }
5601
5602 assert(*success);
5603 assert(varssize >= requiredsize);
5604
5605 SCIPdebugMsg(scip, "successfully parsed %d variables\n", nvars);
5606
5607 /* find "==" */
5608 endptr = strchr(endptr, '=');
5609
5610 /* if the string end has been reached without finding the "==" */
5611 if( endptr == NULL )
5612 {
5613 SCIPerrorMessage("Could not find terminating '='.\n");
5614 *success = FALSE;
5615 goto TERMINATE;
5616 }
5617
5618 str = endptr;
5619
5620 /* skip "==" */
5621 str += *(str+1) == '=' ? 2 : 1;
5622
5623 if( SCIPparseReal(scip, str, &rhs, &endptr) )
5624 {
5625 SCIP_VAR* intvar = NULL;
5626
5627 assert(SCIPisZero(scip, rhs) || SCIPisEQ(scip, rhs, 1.0));
5628
5629 str = endptr;
5630
5631 /* skip white spaces */
5632 SCIP_CALL( SCIPskipSpace((char**)&str) );
5633
5634 /* check for integer variable, should look like (intvar = var) */
5635 if( *str == '(' )
5636 {
5637 str = strchr(str+1, '=');
5638
5639 if( str == NULL )
5640 {
5641 SCIPerrorMessage("Parsing integer variable of XOR constraint\n");
5642 *success = FALSE;
5643 goto TERMINATE;
5644 }
5645
5646 ++str;
5647
5648 /* parse variable name */
5649 SCIP_CALL( SCIPparseVarName(scip, str, &intvar, &endptr) );
5650
5651 if( intvar == NULL )
5652 {
5653 SCIPerrorMessage("Integer variable of XOR not found\n");
5654 *success = FALSE;
5655 goto TERMINATE;
5656 }
5657
5658 /* skip last ')' */
5659 endptr = strchr(endptr, ')');
5660
5661 if( endptr == NULL )
5662 {
5663 SCIPerrorMessage("Closing ')' missing\n");
5664 *success = FALSE;
5665 goto TERMINATE;
5666 }
5667 }
5668
5669 if( intvar != NULL )
5670 {
5671 /* create or constraint */
5672 SCIP_CALL( createConsXorIntvar(scip, cons, name, (rhs > 0.5 ? TRUE : FALSE), nvars, vars, intvar,
5673 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5674 }
5675 else
5676 {
5677 /* create or constraint */
5678 SCIP_CALL( SCIPcreateConsXor(scip, cons, name, (rhs > 0.5 ? TRUE : FALSE), nvars, vars,
5679 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
5680 }
5681
5682 SCIPdebugPrintCons(scip, *cons, NULL);
5683 }
5684 else
5685 *success = FALSE;
5686 }
5687
5688 TERMINATE:
5689 /* free variable buffer */
5691
5692 return SCIP_OKAY;
5693}
5694
5695/** constraint method of constraint handler which returns the variables (if possible) */
5696static
5698{ /*lint --e{715}*/
5699 SCIP_CONSDATA* consdata;
5700 int nintvar = 0;
5701 int cnt;
5702 int j;
5703
5704 consdata = SCIPconsGetData(cons);
5705 assert(consdata != NULL);
5706
5707 if ( consdata->intvar != NULL )
5708 nintvar = 1;
5709
5710 if ( varssize < consdata->nvars + nintvar + consdata->nextvars )
5711 (*success) = FALSE;
5712 else
5713 {
5714 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
5715
5716 if ( consdata->intvar != NULL )
5717 vars[consdata->nvars] = consdata->intvar;
5718
5719 if ( consdata->nextvars > 0 )
5720 {
5721 assert( consdata->extvars != NULL );
5722 cnt = consdata->nvars + nintvar;
5723 for (j = 0; j < consdata->extvarssize; ++j)
5724 {
5725 if ( consdata->extvars[j] != NULL )
5726 vars[cnt++] = consdata->extvars[j];
5727 }
5728 assert( cnt == consdata->nvars + nintvar + consdata->nextvars );
5729 }
5730
5731 (*success) = TRUE;
5732 }
5733
5734 return SCIP_OKAY;
5735}
5736
5737/** constraint method of constraint handler which returns the number of variable (if possible) */
5738static
5740{ /*lint --e{715}*/
5741 SCIP_CONSDATA* consdata;
5742
5743 assert(cons != NULL);
5744
5745 consdata = SCIPconsGetData(cons);
5746 assert(consdata != NULL);
5747
5748 if( consdata->intvar == NULL )
5749 (*nvars) = consdata->nvars + consdata->nextvars;
5750 else
5751 (*nvars) = consdata->nvars + 1 + consdata->nextvars;
5752
5753 (*success) = TRUE;
5754
5755 return SCIP_OKAY;
5756}
5757
5758/*
5759 * Callback methods of event handler
5760 */
5761
5762static
5764{ /*lint --e{715}*/
5765 SCIP_CONSDATA* consdata;
5766
5767 assert(eventhdlr != NULL);
5768 assert(eventdata != NULL);
5769 assert(event != NULL);
5770
5771 consdata = (SCIP_CONSDATA*)eventdata;
5772 assert(consdata != NULL);
5773
5775 {
5776 /* we only catch this event in presolving stage */
5779
5780 consdata->sorted = FALSE;
5781 }
5782
5783 consdata->propagated = FALSE;
5784
5785 return SCIP_OKAY;
5786}
5787
5788
5789/*
5790 * constraint specific interface methods
5791 */
5792
5793/** creates the handler for xor constraints and includes it in SCIP */
5795 SCIP* scip /**< SCIP data structure */
5796 )
5797{
5798 SCIP_CONSHDLRDATA* conshdlrdata;
5799 SCIP_CONSHDLR* conshdlr;
5800 SCIP_EVENTHDLR* eventhdlr;
5801
5802 /* create event handler for events on variables */
5804 eventExecXor, NULL) );
5805
5806 /* create constraint handler data */
5807 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
5808
5809 /* include constraint handler */
5813 conshdlrdata) );
5814 assert(conshdlr != NULL);
5815
5816 /* set non-fundamental callbacks via specific setter functions */
5836
5837 if ( SCIPfindConshdlr(scip, "linear") != NULL )
5838 {
5839 /* include the linear constraint upgrade in the linear constraint handler */
5841 }
5842
5843 /* add xor constraint handler parameters */
5845 "constraints/xor/presolpairwise",
5846 "should pairwise constraint comparison be performed in presolving?",
5847 &conshdlrdata->presolpairwise, TRUE, DEFAULT_PRESOLPAIRWISE, NULL, NULL) );
5848
5850 "constraints/xor/presolusehashing",
5851 "should hash table be used for detecting redundant constraints in advance?",
5852 &conshdlrdata->presolusehashing, TRUE, DEFAULT_PRESOLUSEHASHING, NULL, NULL) );
5853
5855 "constraints/xor/addextendedform",
5856 "should the extended formulation be added in presolving?",
5857 &conshdlrdata->addextendedform, TRUE, DEFAULT_ADDEXTENDEDFORM, NULL, NULL) );
5858
5860 "constraints/xor/addflowextended",
5861 "should the extended flow formulation be added (nonsymmetric formulation otherwise)?",
5862 &conshdlrdata->addflowextended, TRUE, DEFAULT_ADDFLOWEXTENDED, NULL, NULL) );
5863
5865 "constraints/xor/separateparity",
5866 "should parity inequalities be separated?",
5867 &conshdlrdata->separateparity, TRUE, DEFAULT_SEPARATEPARITY, NULL, NULL) );
5868
5870 "constraints/xor/gausspropfreq",
5871 "frequency for applying the Gauss propagator",
5872 &conshdlrdata->gausspropfreq, TRUE, DEFAULT_GAUSSPROPFREQ, -1, SCIP_MAXTREEDEPTH, NULL, NULL) );
5873
5874 return SCIP_OKAY;
5875}
5876
5877/** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs
5878 *
5879 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5880 */
5882 SCIP* scip, /**< SCIP data structure */
5883 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5884 const char* name, /**< name of constraint */
5885 SCIP_Bool rhs, /**< right hand side of the constraint */
5886 int nvars, /**< number of operator variables in the constraint */
5887 SCIP_VAR** vars, /**< array with operator variables of constraint */
5888 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
5889 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
5890 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
5891 * Usually set to TRUE. */
5892 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
5893 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5894 SCIP_Bool check, /**< should the constraint be checked for feasibility?
5895 * TRUE for model constraints, FALSE for additional, redundant constraints. */
5896 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
5897 * Usually set to TRUE. */
5898 SCIP_Bool local, /**< is constraint only valid locally?
5899 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
5900 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
5901 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
5902 * adds coefficients to this constraint. */
5903 SCIP_Bool dynamic, /**< is constraint subject to aging?
5904 * Usually set to FALSE. Set to TRUE for own cuts which
5905 * are separated as constraints. */
5906 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
5907 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
5908 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
5909 * if it may be moved to a more global node?
5910 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
5911 )
5912{
5913 SCIP_CONSHDLR* conshdlr;
5914 SCIP_CONSDATA* consdata;
5915
5916 /* find the xor constraint handler */
5917 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
5918 if( conshdlr == NULL )
5919 {
5920 SCIPerrorMessage("xor constraint handler not found\n");
5921 return SCIP_PLUGINNOTFOUND;
5922 }
5923
5924 /* create constraint data */
5925 SCIP_CALL( consdataCreate(scip, &consdata, rhs, nvars, vars, NULL) );
5926
5927 /* create constraint */
5928 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
5929 local, modifiable, dynamic, removable, stickingatnode) );
5930
5931 return SCIP_OKAY;
5932}
5933
5934/** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs
5935 * with all constraint flags set to their default values
5936 *
5937 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
5938 */
5940 SCIP* scip, /**< SCIP data structure */
5941 SCIP_CONS** cons, /**< pointer to hold the created constraint */
5942 const char* name, /**< name of constraint */
5943 SCIP_Bool rhs, /**< right hand side of the constraint */
5944 int nvars, /**< number of operator variables in the constraint */
5945 SCIP_VAR** vars /**< array with operator variables of constraint */
5946 )
5947{
5948 SCIP_CALL( SCIPcreateConsXor(scip,cons, name, rhs, nvars, vars,
5950
5951 return SCIP_OKAY;
5952}
5953
5954/** gets number of variables in xor constraint */
5956 SCIP* scip, /**< SCIP data structure */
5957 SCIP_CONS* cons /**< constraint data */
5958 )
5959{
5960 SCIP_CONSDATA* consdata;
5961
5962 assert(scip != NULL);
5963
5965 {
5966 SCIPerrorMessage("constraint is not an xor constraint\n");
5967 SCIPABORT();
5968 return -1; /*lint !e527*/
5969 }
5970
5971 consdata = SCIPconsGetData(cons);
5972 assert(consdata != NULL);
5973
5974 return consdata->nvars;
5975}
5976
5977/** gets array of variables in xor constraint */
5979 SCIP* scip, /**< SCIP data structure */
5980 SCIP_CONS* cons /**< constraint data */
5981 )
5982{
5983 SCIP_CONSDATA* consdata;
5984
5985 assert(scip != NULL);
5986
5988 {
5989 SCIPerrorMessage("constraint is not an xor constraint\n");
5990 SCIPABORT();
5991 return NULL; /*lint !e527*/
5992 }
5993
5994 consdata = SCIPconsGetData(cons);
5995 assert(consdata != NULL);
5996
5997 return consdata->vars;
5998}
5999
6000/** gets integer variable in xor constraint */
6002 SCIP* scip, /**< SCIP data structure */
6003 SCIP_CONS* cons /**< constraint data */
6004 )
6005{
6006 SCIP_CONSDATA* consdata;
6007
6008 assert(scip != NULL);
6009
6011 {
6012 SCIPerrorMessage("constraint is not an xor constraint\n");
6013 SCIPABORT();
6014 return NULL; /*lint !e527*/
6015 }
6016
6017 consdata = SCIPconsGetData(cons);
6018 assert(consdata != NULL);
6019
6020 return consdata->intvar;
6021}
6022
6023/** gets the right hand side of the xor constraint */
6025 SCIP* scip, /**< SCIP data structure */
6026 SCIP_CONS* cons /**< constraint data */
6027 )
6028{
6029 SCIP_CONSDATA* consdata;
6030
6031 assert(scip != NULL);
6032
6034 {
6035 SCIPerrorMessage("constraint is not an xor constraint\n");
6036 SCIPABORT();
6037 }
6038
6039 consdata = SCIPconsGetData(cons);
6040 assert(consdata != NULL);
6041
6042 return consdata->rhs;
6043}
SCIP_VAR * h
SCIP_VAR ** b
SCIP_VAR ** x
enum Proprule PROPRULE
Definition cons_and.c:176
Proprule
Definition cons_and.c:169
Constraint handler for linear constraints in their most general form, .
Constraint handler for the set partitioning / packing / covering constraints .
static SCIP_RETCODE addRelaxation(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
Definition cons_xor.c:1784
enum Proprule PROPRULE
Definition cons_xor.c:178
static SCIP_RETCODE consdataFreeRows(SCIP *scip, SCIP_CONSDATA *consdata)
Definition cons_xor.c:426
static SCIP_RETCODE addCoef(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_xor.c:595
#define DEFAULT_SEPARATEPARITY
Definition cons_xor.c:112
static SCIP_RETCODE consdataSwitchWatchedvars(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2)
Definition cons_xor.c:252
#define CONSHDLR_NEEDSCONS
Definition cons_xor.c:99
#define CONSHDLR_SEPAFREQ
Definition cons_xor.c:92
static SCIP_RETCODE addExtendedAsymmetricFormulation(SCIP *scip, SCIP_CONS *cons, int *naggrvars, int *naddedconss)
Definition cons_xor.c:1470
static SCIP_RETCODE checkSystemGF2(SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *currentsol, SCIP_RESULT *result)
Definition cons_xor.c:2336
static SCIP_RETCODE delCoefPos(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos)
Definition cons_xor.c:661
#define CONSHDLR_CHECKPRIORITY
Definition cons_xor.c:91
static SCIP_RETCODE setIntvar(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_xor.c:543
static SCIP_RETCODE checkCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool *violated)
Definition cons_xor.c:1838
#define CONSHDLR_DESC
Definition cons_xor.c:88
#define DEFAULT_ADDFLOWEXTENDED
Definition cons_xor.c:111
static SCIP_RETCODE createRelaxation(SCIP *scip, SCIP_CONS *cons)
Definition cons_xor.c:1651
#define CONSHDLR_PROP_TIMING
Definition cons_xor.c:101
static void conshdlrdataFree(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata)
Definition cons_xor.c:239
#define DEFAULT_GAUSSPROPFREQ
Definition cons_xor.c:113
static SCIP_RETCODE unlockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_xor.c:203
#define HASHSIZE_XORCONS
Definition cons_xor.c:114
#define CONSHDLR_MAXPREROUNDS
Definition cons_xor.c:96
static SCIP_RETCODE cliquePresolve(SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *ndelconss, int *naddconss, SCIP_Bool *cutoff)
Definition cons_xor.c:3400
#define DEFAULT_PRESOLPAIRWISE
Definition cons_xor.c:109
#define CONSHDLR_SEPAPRIORITY
Definition cons_xor.c:89
static SCIP_RETCODE analyzeConflict(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule)
Definition cons_xor.c:2927
static SCIP_Bool allRowsInLP(SCIP_CONSDATA *consdata)
Definition cons_xor.c:1816
#define MAXXORCONSSSYSTEM
Definition cons_xor.c:118
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_Bool rhs, int nvars, SCIP_VAR **vars, SCIP_VAR *intvar)
Definition cons_xor.c:340
static SCIP_RETCODE lockRounding(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
Definition cons_xor.c:187
static SCIP_RETCODE consdataEnsureVarsSize(SCIP *scip, SCIP_CONSDATA *consdata, int num)
Definition cons_xor.c:316
@ PROPRULE_1
Definition cons_xor.c:173
@ PROPRULE_INTUB
Definition cons_xor.c:175
@ PROPRULE_0
Definition cons_xor.c:172
@ PROPRULE_INTLB
Definition cons_xor.c:174
@ PROPRULE_INVALID
Definition cons_xor.c:176
#define DEFAULT_PRESOLUSEHASHING
Definition cons_xor.c:115
static void solveRowEchelonGF2(int m, int n, int r, int *p, int *s, Type **A, Type *b, Type *x)
Definition cons_xor.c:2275
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr)
Definition cons_xor.c:448
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *nchgbds)
Definition cons_xor.c:2958
#define MINGAINPERNMINCOMPARISONS
Definition cons_xor.c:117
static SCIP_RETCODE addExtendedFlowFormulation(SCIP *scip, SCIP_CONS *cons, int *naggrvars, int *naddedconss)
Definition cons_xor.c:1161
static SCIP_RETCODE addConflictBounds(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, SCIP_BDCHGIDX *bdchgidx, PROPRULE proprule)
Definition cons_xor.c:2819
#define CONSHDLR_PROPFREQ
Definition cons_xor.c:93
static SCIP_RETCODE separateCons(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool separateparity, SCIP_Bool *separated, SCIP_Bool *cutoff)
Definition cons_xor.c:1953
#define NMINCOMPARISONS
Definition cons_xor.c:116
#define CONSHDLR_PRESOLTIMING
Definition cons_xor.c:102
static SCIP_RETCODE detectRedundantConstraints(SCIP *scip, BMS_BLKMEM *blkmem, SCIP_CONS **conss, int nconss, int *firstchange, int *nchgcoefs, int *nfixedvars, int *naggrvars, int *ndelconss, int *naddconss, SCIP_Bool *cutoff)
Definition cons_xor.c:3693
#define MAXXORVARSSYSTEM
Definition cons_xor.c:119
static void consdataSort(SCIP_CONSDATA *consdata)
Definition cons_xor.c:722
static SCIP_RETCODE preprocessConstraintPairs(SCIP *scip, SCIP_CONS **conss, int firstchange, int chkind, SCIP_Bool *cutoff, int *nfixedvars, int *naggrvars, int *ndelconss, int *naddconss, int *nchgcoefs)
Definition cons_xor.c:3890
#define CONSHDLR_EAGERFREQ
Definition cons_xor.c:94
#define DEFAULT_ADDEXTENDEDFORM
Definition cons_xor.c:110
unsigned short Type
Definition cons_xor.c:129
#define EVENTHDLR_DESC
Definition cons_xor.c:105
static SCIP_RETCODE conshdlrdataCreate(SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr)
Definition cons_xor.c:219
static SCIP_RETCODE createConsXorIntvar(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_Bool rhs, int nvars, SCIP_VAR **vars, SCIP_VAR *intvar, 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 cons_xor.c:4473
#define NROWS
Definition cons_xor.c:121
#define CONSHDLR_ENFOPRIORITY
Definition cons_xor.c:90
#define LINCONSUPGD_PRIORITY
Definition cons_xor.c:107
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
Definition cons_xor.c:3379
#define CONSHDLR_DELAYSEPA
Definition cons_xor.c:97
static int computeRowEchelonGF2(SCIP *scip, int m, int n, int *p, int *s, Type **A, Type *b)
Definition cons_xor.c:2166
#define CONSHDLR_NAME
Definition cons_xor.c:87
#define EVENTHDLR_NAME
Definition cons_xor.c:104
static SCIP_RETCODE applyFixings(SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int *nchgcoefs, int *naggrvars, int *naddconss, SCIP_Bool *cutoff)
Definition cons_xor.c:888
#define CONSHDLR_DELAYPROP
Definition cons_xor.c:98
static SCIP_RETCODE consdataPrint(SCIP *scip, SCIP_CONSDATA *consdata, FILE *file, SCIP_Bool endline)
Definition cons_xor.c:509
Constraint handler for XOR constraints, .
methods for debugging
#define SCIPdebugGetSolVal(scip, var, val)
Definition debug.h:299
#define SCIPdebugAddSolVal(scip, var, val)
Definition debug.h:298
#define SCIP_MAXSTRLEN
Definition def.h:302
#define SCIP_Longint
Definition def.h:171
#define SCIP_MAXTREEDEPTH
Definition def.h:330
#define SCIP_Bool
Definition def.h:93
#define SCIP_Real
Definition def.h:186
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define SCIPABORT()
Definition def.h:360
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
SCIP_RETCODE SCIPincludeLinconsUpgrade(SCIP *scip, SCIP_DECL_LINCONSUPGD((*linconsupgd)), int priority, const char *conshdlrname)
int SCIPgetNVarsXor(SCIP *scip, SCIP_CONS *cons)
Definition cons_xor.c:5955
SCIP_RETCODE SCIPcreateConsBasicXor(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_Bool rhs, int nvars, SCIP_VAR **vars)
Definition cons_xor.c:5939
SCIP_VAR * SCIPgetIntVarXor(SCIP *scip, SCIP_CONS *cons)
Definition cons_xor.c:6001
SCIP_RETCODE SCIPcreateConsXor(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_Bool rhs, 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)
Definition cons_xor.c:5881
SCIP_RETCODE SCIPaddCoefSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var)
#define SCIP_DECL_LINCONSUPGD(x)
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_RETCODE SCIPcreateConsSetpart(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_Bool SCIPgetRhsXor(SCIP *scip, SCIP_CONS *cons)
Definition cons_xor.c:6024
SCIP_VAR ** SCIPgetVarsXor(SCIP *scip, SCIP_CONS *cons)
Definition cons_xor.c:5978
SCIP_RETCODE SCIPincludeConshdlrXor(SCIP *scip)
Definition cons_xor.c:5794
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition scip_copy.c:711
SCIP_Bool SCIPisTransformed(SCIP *scip)
SCIP_Bool SCIPisPresolveFinished(SCIP *scip)
SCIP_Bool SCIPisStopped(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
Definition scip_prob.c:1668
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
SCIP_VAR ** SCIPgetVars(SCIP *scip)
Definition scip_prob.c:1947
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 SCIPdelConsLocal(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3474
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_RETCODE SCIPheurPassSolAddSol(SCIP *scip, SCIP_HEUR *heur, SCIP_SOL *sol)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
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
void SCIPswapPointers(void **pointer1, void **pointer2)
Definition misc.c:10307
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
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 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_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4200
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_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_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_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 SCIPconsIsLockedType(SCIP_CONS *cons, SCIP_LOCKTYPE locktype)
Definition cons.c:8481
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
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_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 SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
Definition scip_cons.c:1119
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8267
SCIP_RETCODE SCIPincConsAge(SCIP *scip, SCIP_CONS *cons)
Definition scip_cons.c:1730
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8357
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition scip_cut.c:135
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
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_HEUR * SCIPfindHeur(SCIP *scip, const char *name)
Definition scip_heur.c:258
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
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 SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIP_Bool SCIPinProbing(SCIP *scip)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1635
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1993
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 SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition scip_lp.c:1658
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition scip_lp.c:1701
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition scip_lp.c:2212
SCIP_Real SCIPgetRowSolFeasibility(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
Definition scip_lp.c:2167
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1562
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition lp.c:17523
SCIP_RETCODE SCIPprintSol(SCIP *scip, SCIP_SOL *sol, FILE *file, SCIP_Bool printzeros)
Definition scip_sol.c:1775
void SCIPupdateSolConsViolation(SCIP *scip, SCIP_SOL *sol, SCIP_Real absviol, SCIP_Real relviol)
Definition scip_sol.c:273
SCIP_RETCODE SCIPcheckSol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *feasible)
Definition scip_sol.c:3391
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition scip_sol.c:1221
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1361
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfeasFloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPparseReal(SCIP *scip, const char *str, SCIP_Real *value, char **endptr)
SCIP_Bool SCIPinRepropagation(SCIP *scip)
Definition scip_tree.c:146
int SCIPgetDepth(SCIP *scip)
Definition scip_tree.c:670
SCIP_Bool SCIPvarIsInitial(SCIP_VAR *var)
Definition var.c:17442
int SCIPvarCompareActiveAndNegated(SCIP_VAR *var1, SCIP_VAR *var2)
Definition var.c:11893
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5203
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 SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition scip_var.c:1480
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:17360
int SCIPvarGetNLocksUpType(SCIP_VAR *var, SCIP_LOCKTYPE locktype)
Definition var.c:3353
SCIP_Real SCIPvarGetAggrConstant(SCIP_VAR *var)
Definition var.c:17656
SCIP_Bool SCIPdoNotAggr(SCIP *scip)
Definition scip_var.c:8565
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:17966
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_RETCODE SCIPaggregateVars(SCIP *scip, SCIP_VAR *varx, SCIP_VAR *vary, SCIP_Real scalarx, SCIP_Real scalary, SCIP_Real rhs, SCIP_Bool *infeasible, SCIP_Bool *redundant, SCIP_Bool *aggregated)
Definition scip_var.c:8401
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5615
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:17748
SCIP_Real SCIPvarGetAggrScalar(SCIP_VAR *var)
Definition var.c:17644
SCIP_VAR * SCIPvarGetProbvar(SCIP_VAR *var)
Definition var.c:12207
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5320
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition scip_var.c:533
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
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17241
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
SCIP_Bool SCIPvarIsRemovable(SCIP_VAR *var)
Definition var.c:17452
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:17956
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition var.c:17396
SCIP_Real SCIPcomputeVarLbLocal(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:6505
SCIP_VAR * SCIPvarGetNegationVar(SCIP_VAR *var)
Definition var.c:17726
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
Definition scip_var.c:114
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_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition scip_var.c:5501
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 SCIPprintVar(SCIP *scip, SCIP_VAR *var, FILE *file)
Definition scip_var.c:9885
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 SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition scip_var.c:230
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition scip_var.c:1597
SCIP_RETCODE SCIPwriteVarsList(SCIP *scip, FILE *file, SCIP_VAR **vars, int nvars, SCIP_Bool type, char delimiter)
Definition scip_var.c:292
SCIP_Real SCIPcomputeVarUbLocal(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:6526
SCIP_Bool SCIPvarsHaveCommonClique(SCIP_VAR *var1, SCIP_Bool value1, SCIP_VAR *var2, SCIP_Bool value2, SCIP_Bool regardimplics)
Definition var.c:11464
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_VAR * SCIPvarGetAggrVar(SCIP_VAR *var)
Definition var.c:17632
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortRealIntPtr(SCIP_Real *realarray, int *intarray, void **ptrarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10788
SCIP_RETCODE SCIPskipSpace(char **s)
Definition misc.c:10777
return SCIP_OKAY
SCIPfreeSol(scip, &heurdata->sol))
SCIPcreateSol(scip, &heurdata->sol, heur))
int c
int depth
SCIP_Bool cutoff
static SCIP_SOL * sol
int r
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_Bool propagate
static SCIP_VAR ** vars
primal heuristic that tries a given solution
#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
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 problem copies
public methods for cuts and aggregation rows
public methods for event handler plugins and event handlers
general public methods
public methods for primal heuristic plugins and divesets
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
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 the branch-and-bound tree
public methods for SCIP variables
#define MAX(x, y)
Definition tclique_def.h:92
@ 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_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_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_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
#define SCIP_EVENTTYPE_BOUNDCHANGED
Definition type_event.h:125
struct SCIP_EventData SCIP_EVENTDATA
Definition type_event.h:173
#define SCIP_EVENTTYPE_VARFIXED
Definition type_event.h:72
#define SCIP_DECL_EVENTEXEC(x)
Definition type_event.h:253
#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_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_SEPARATED
Definition type_result.h:49
@ 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_PLUGINNOTFOUND
@ 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_EXITPRESOLVE
Definition type_set.h:50
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
#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_VARSTATUS_AGGREGATED
Definition type_var.h:53
@ SCIP_LOCKTYPE_CONFLICT
Definition type_var.h:98
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:97
enum SCIP_Vartype SCIP_VARTYPE
Definition type_var.h:73