Scippy

SCIP

Solving Constraint Integer Programs

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-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file cons_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#include "scip/symmetry_graph.h"
86#include <string.h>
87
88/* constraint handler properties */
89#define CONSHDLR_NAME "xor"
90#define CONSHDLR_DESC "constraint handler for xor constraints: r = xor(x1, ..., xn)"
91#define CONSHDLR_SEPAPRIORITY +850200 /**< priority of the constraint handler for separation */
92#define CONSHDLR_ENFOPRIORITY -850200 /**< priority of the constraint handler for constraint enforcing */
93#define CONSHDLR_CHECKPRIORITY -850200 /**< priority of the constraint handler for checking feasibility */
94#define CONSHDLR_SEPAFREQ 0 /**< frequency for separating cuts; zero means to separate only in the root node */
95#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
96#define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
97 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
98#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
99#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
100#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
101#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
102
103#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
104#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS
105
106#define EVENTHDLR_NAME "xor"
107#define EVENTHDLR_DESC "event handler for xor constraints"
108
109#define LINCONSUPGD_PRIORITY +600000 /**< priority of the constraint handler for upgrading of linear constraints */
110
111#define DEFAULT_PRESOLPAIRWISE TRUE /**< should pairwise constraint comparison be performed in presolving? */
112#define DEFAULT_ADDEXTENDEDFORM FALSE /**< should the extended formulation be added in presolving? */
113#define DEFAULT_ADDFLOWEXTENDED FALSE /**< should the extended flow formulation be added (nonsymmetric formulation otherwise)? */
114#define DEFAULT_SEPARATEPARITY FALSE /**< should parity inequalities be separated? */
115#define DEFAULT_GAUSSPROPFREQ 5 /**< frequency for applying the Gauss propagator */
116#define HASHSIZE_XORCONS 500 /**< minimal size of hash table in logicor constraint tables */
117#define DEFAULT_PRESOLUSEHASHING TRUE /**< should hash table be used for detecting redundant constraints in advance */
118#define NMINCOMPARISONS 200000 /**< number for minimal pairwise presolving comparisons */
119#define MINGAINPERNMINCOMPARISONS 1e-06 /**< minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round */
120#define MAXXORCONSSSYSTEM 1000 /**< maximal number of active constraints for which checking the system over GF2 is performed */
121#define MAXXORVARSSYSTEM 1000 /**< maximal number of variables in xor constraints for which checking the system over GF2 is performed */
122
123#define NROWS 5
124
125
126/*
127 * Data structures
128 */
129
130/** type used for matrix entries in function checkGauss() */
131typedef unsigned short Type;
132
133/** constraint data for xor constraints */
134struct SCIP_ConsData
135{
136 SCIP_VAR** vars; /**< variables in the xor operation */
137 SCIP_VAR* intvar; /**< internal variable for LP relaxation */
138 SCIP_VAR** extvars; /**< variables in extended (flow|asymmetric) formulation (order for flow formulation: nn, ns, sn, ss) */
139 SCIP_ROW* rows[NROWS]; /**< rows for linear relaxation of xor constraint */
140 int nvars; /**< number of variables in xor operation */
141 int nextvars; /**< number of variables in extended flow formulation */
142 int varssize; /**< size of vars array */
143 int extvarssize; /**< size of extvars array */
144 int watchedvar1; /**< position of first watched operator variable */
145 int watchedvar2; /**< position of second watched operator variable */
146 int filterpos1; /**< event filter position of first watched operator variable */
147 int filterpos2; /**< event filter position of second watched operator variable */
148 SCIP_Bool rhs; /**< right hand side of the constraint */
149 unsigned int deleteintvar:1; /**< should artificial variable be deleted */
150 unsigned int propagated:1; /**< is constraint already preprocessed/propagated? */
151 unsigned int sorted:1; /**< are the constraint's variables sorted? */
152 unsigned int changed:1; /**< was constraint changed since last pair preprocessing round? */
153};
154
155/** constraint handler data */
156struct SCIP_ConshdlrData
157{
158 SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
159 SCIP_Bool presolpairwise; /**< should pairwise constraint comparison be performed in presolving? */
160 SCIP_Bool presolusehashing; /**< should hash table be used for detecting redundant constraints in advance? */
161 SCIP_Bool addextendedform; /**< should the extended formulation be added in presolving? */
162 SCIP_Bool addflowextended; /**< should the extended flow formulation be added (nonsymmetric formulation otherwise)? */
163 SCIP_Bool separateparity; /**< should parity inequalities be separated? */
164 int gausspropfreq; /**< frequency for applying the Gauss propagator */
165};
166
167
168/*
169 * Propagation rules
170 */
171
173{
174 PROPRULE_0, /**< all variables are fixed => fix integral variable */
175 PROPRULE_1, /**< all except one variable fixed => fix remaining variable */
176 PROPRULE_INTLB, /**< lower bound propagation of integral variable */
177 PROPRULE_INTUB, /**< upper bound propagation of integral variable */
178 PROPRULE_INVALID /**< propagation was applied without a specific propagation rule */
180typedef enum Proprule PROPRULE;
181
182
183/*
184 * Local methods
185 */
186
187/** installs rounding locks for the given variable in the given xor constraint */
188static
190 SCIP* scip, /**< SCIP data structure */
191 SCIP_CONS* cons, /**< xor constraint */
192 SCIP_VAR* var /**< variable of constraint entry */
193 )
194{
196
197 /* rounding in both directions may violate the constraint */
198 SCIP_CALL( SCIPlockVarCons(scip, var, cons, TRUE, TRUE) );
199
200 return SCIP_OKAY;
201}
202
203/** removes rounding locks for the given variable in the given xor constraint */
204static
206 SCIP* scip, /**< SCIP data structure */
207 SCIP_CONS* cons, /**< xor constraint */
208 SCIP_VAR* var /**< variable of constraint entry */
209 )
210{
212
213 /* rounding in both directions may violate the constraint */
214 SCIP_CALL( SCIPunlockVarCons(scip, var, cons, TRUE, TRUE) );
215
216 return SCIP_OKAY;
217}
218
219/** creates constraint handler data */
220static
222 SCIP* scip, /**< SCIP data structure */
223 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
224 SCIP_EVENTHDLR* eventhdlr /**< event handler */
225 )
226{
227 assert(scip != NULL);
228 assert(conshdlrdata != NULL);
229 assert(eventhdlr != NULL);
230
231 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
232
233 /* set event handler for catching events on watched variables */
234 (*conshdlrdata)->eventhdlr = eventhdlr;
235
236 return SCIP_OKAY;
237}
238
239/** frees constraint handler data */
240static
242 SCIP* scip, /**< SCIP data structure */
243 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
244 )
245{
246 assert(conshdlrdata != NULL);
247 assert(*conshdlrdata != NULL);
248
249 SCIPfreeBlockMemory(scip, conshdlrdata);
250}
251
252/** stores the given variable numbers as watched variables, and updates the event processing */
253static
255 SCIP* scip, /**< SCIP data structure */
256 SCIP_CONSDATA* consdata, /**< xor constraint data */
257 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
258 int watchedvar1, /**< new first watched variable */
259 int watchedvar2 /**< new second watched variable */
260 )
261{
262 assert(consdata != NULL);
263 assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
264 assert(watchedvar1 != -1 || watchedvar2 == -1);
265 assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
266 assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
267
268 /* if one watched variable is equal to the old other watched variable, just switch positions */
269 if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
270 {
271 int tmp;
272
273 tmp = consdata->watchedvar1;
274 consdata->watchedvar1 = consdata->watchedvar2;
275 consdata->watchedvar2 = tmp;
276 tmp = consdata->filterpos1;
277 consdata->filterpos1 = consdata->filterpos2;
278 consdata->filterpos2 = tmp;
279 }
280 assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
281 assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
282
283 /* drop events on old watched variables */
284 if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
285 {
286 assert(consdata->filterpos1 != -1);
287 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar1], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
288 (SCIP_EVENTDATA*)consdata, consdata->filterpos1) );
289 }
290 if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
291 {
292 assert(consdata->filterpos2 != -1);
293 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[consdata->watchedvar2], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
294 (SCIP_EVENTDATA*)consdata, consdata->filterpos2) );
295 }
296
297 /* catch events on new watched variables */
298 if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
299 {
300 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar1], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
301 (SCIP_EVENTDATA*)consdata, &consdata->filterpos1) );
302 }
303 if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
304 {
305 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[watchedvar2], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr,
306 (SCIP_EVENTDATA*)consdata, &consdata->filterpos2) );
307 }
308
309 /* set the new watched variables */
310 consdata->watchedvar1 = watchedvar1;
311 consdata->watchedvar2 = watchedvar2;
312
313 return SCIP_OKAY;
314}
315
316/** ensures, that the vars array can store at least num entries */
317static
319 SCIP* scip, /**< SCIP data structure */
320 SCIP_CONSDATA* consdata, /**< linear constraint data */
321 int num /**< minimum number of entries to store */
322 )
323{
324 assert(consdata != NULL);
325 assert(consdata->nvars <= consdata->varssize);
326
327 if( num > consdata->varssize )
328 {
329 int newsize;
330
331 newsize = SCIPcalcMemGrowSize(scip, num);
332 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
333 consdata->varssize = newsize;
334 }
335 assert(num <= consdata->varssize);
336
337 return SCIP_OKAY;
338}
339
340/** creates constraint data for xor constraint */
341static
343 SCIP* scip, /**< SCIP data structure */
344 SCIP_CONSDATA** consdata, /**< pointer to store the constraint data */
345 SCIP_Bool rhs, /**< right hand side of the constraint */
346 int nvars, /**< number of variables in the xor operation */
347 SCIP_VAR** vars, /**< variables in xor operation */
348 SCIP_VAR* intvar /**< artificial integer variable for linear relaxation */
349 )
350{
351 int r;
352
353 assert(consdata != NULL);
354 assert(nvars == 0 || vars != NULL);
355
356 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
357 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
358
359 (*consdata)->rhs = rhs;
360 (*consdata)->intvar = intvar;
361 for( r = 0; r < NROWS; ++r )
362 (*consdata)->rows[r] = NULL;
363 (*consdata)->nvars = nvars;
364 (*consdata)->varssize = nvars;
365 (*consdata)->watchedvar1 = -1;
366 (*consdata)->watchedvar2 = -1;
367 (*consdata)->filterpos1 = -1;
368 (*consdata)->filterpos2 = -1;
369 (*consdata)->deleteintvar = (intvar == NULL);
370 (*consdata)->propagated = FALSE;
371 (*consdata)->sorted = FALSE;
372 (*consdata)->changed = TRUE;
373 (*consdata)->extvars = NULL;
374 (*consdata)->nextvars = 0;
375 (*consdata)->extvarssize = 0;
376
377 /* get transformed variables, if we are in the transformed problem */
379 {
380 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
381
382 if( (*consdata)->intvar != NULL )
383 {
384 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->intvar, &((*consdata)->intvar)) );
385 }
386
388 {
389 SCIP_CONSHDLRDATA* conshdlrdata;
390 SCIP_CONSHDLR* conshdlr;
391 int v;
392
394 assert(conshdlr != NULL);
395 conshdlrdata = SCIPconshdlrGetData(conshdlr);
396 assert(conshdlrdata != NULL);
397
398 for( v = (*consdata)->nvars - 1; v >= 0; --v )
399 {
400 SCIP_CALL( SCIPcatchVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
401 (SCIP_EVENTDATA*)(*consdata), NULL) );
402 }
403 }
404 }
405
406 if( (*consdata)->intvar != NULL )
407 {
408 /* capture artificial variable */
409 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->intvar) );
410 }
411
412 return SCIP_OKAY;
413}
414
415/** releases LP row of constraint data */
416static
418 SCIP* scip, /**< SCIP data structure */
419 SCIP_CONSDATA* consdata /**< constraint data */
420 )
421{
422 int r;
423
424 assert(consdata != NULL);
425
426 for( r = 0; r < NROWS; ++r )
427 {
428 if( consdata->rows[r] != NULL )
429 {
430 SCIP_CALL( SCIPreleaseRow(scip, &consdata->rows[r]) );
431 }
432 }
433
434 return SCIP_OKAY;
435}
436
437/** frees constraint data for xor constraint */
438static
440 SCIP* scip, /**< SCIP data structure */
441 SCIP_CONSDATA** consdata, /**< pointer to the constraint data */
442 SCIP_EVENTHDLR* eventhdlr /**< event handler to call for the event processing */
443 )
444{
445 assert(consdata != NULL);
446 assert(*consdata != NULL);
447
449 {
450 int j;
451
452 /* drop events for watched variables */
453 SCIP_CALL( consdataSwitchWatchedvars(scip, *consdata, eventhdlr, -1, -1) );
454
455 /* release flow variables */
456 if ( (*consdata)->nextvars > 0 )
457 {
458 assert( (*consdata)->extvars != NULL );
459 for (j = 0; j < (*consdata)->extvarssize; ++j)
460 {
461 if ( (*consdata)->extvars[j] != NULL )
462 {
463 SCIP_CALL( SCIPreleaseVar(scip, &((*consdata)->extvars[j])) );
464 }
465 }
466
467 SCIPfreeBlockMemoryArray(scip, &((*consdata)->extvars), (*consdata)->extvarssize);
468 (*consdata)->nextvars = 0;
469 (*consdata)->extvarssize = 0;
470 }
471 }
472 else
473 {
474 assert((*consdata)->watchedvar1 == -1);
475 assert((*consdata)->watchedvar2 == -1);
476 }
477
478 /* release LP row */
479 SCIP_CALL( consdataFreeRows(scip, *consdata) );
480
481 /* release internal variable */
482 if( (*consdata)->intvar != NULL )
483 {
484 /* if the constraint is deleted and the integral variable is present, it should be fixed */
485 assert( SCIPisEQ(scip, SCIPvarGetLbGlobal((*consdata)->intvar), SCIPvarGetLbGlobal((*consdata)->intvar)) );
486
487 /* We do not delete the integral variable, but leave the handling to SCIP, because it might happen that the
488 integral variable is stored in some basis information somewhere. */
489 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->intvar) );
490 }
491
492 SCIPfreeBlockMemoryArray(scip, &(*consdata)->vars, (*consdata)->varssize);
493 SCIPfreeBlockMemory(scip, consdata);
494
495 return SCIP_OKAY;
496}
497
498/** prints xor constraint to file stream */
499static
501 SCIP* scip, /**< SCIP data structure */
502 SCIP_CONSDATA* consdata, /**< xor constraint data */
503 FILE* file, /**< output file (or NULL for standard output) */
504 SCIP_Bool endline /**< should an endline be set? */
505 )
506{
507 assert(consdata != NULL);
508
509 /* start variable list */
510 SCIPinfoMessage(scip, file, "xor(");
511
512 /* print variable list */
513 SCIP_CALL( SCIPwriteVarsList(scip, file, consdata->vars, consdata->nvars, TRUE, ',') );
514
515 /* close variable list and write right hand side */
516 SCIPinfoMessage(scip, file, ") = %u", consdata->rhs);
517
518 /* write integer variable if it exists */
519 if( consdata->intvar != NULL )
520 {
521 SCIPinfoMessage(scip, file, " (intvar = ");
522 SCIP_CALL( SCIPwriteVarName(scip, file, consdata->intvar, TRUE) );
523 SCIPinfoMessage(scip, file, ")");
524 }
525
526 if( endline )
527 SCIPinfoMessage(scip, file, "\n");
528
529 return SCIP_OKAY;
530}
531
532/** sets intvar of an xor constraint */
533static
535 SCIP* scip, /**< SCIP data structure */
536 SCIP_CONS* cons, /**< xor constraint */
537 SCIP_VAR* var /**< variable to add to the constraint */
538 )
539{
540 SCIP_CONSDATA* consdata;
541 SCIP_Bool transformed;
542
543 assert(var != NULL);
544
545 consdata = SCIPconsGetData(cons);
546 assert(consdata != NULL);
547 assert(consdata->rows[0] == NULL);
548
549 /* are we in the transformed problem? */
550 transformed = SCIPconsIsTransformed(cons);
551
552 /* always use transformed variables in transformed constraints */
553 if( transformed )
554 {
555 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
556 }
557 assert(var != NULL);
558 assert(transformed == SCIPvarIsTransformed(var));
559
560 /* remove the rounding locks for the old variable and release it */
561 if( consdata->intvar != NULL )
562 {
563 SCIP_CALL( unlockRounding(scip, cons, consdata->intvar) );
564 SCIP_CALL( SCIPreleaseVar(scip, &(consdata->intvar)) );
565 }
566
567 consdata->intvar = var;
568 consdata->changed = TRUE;
569
570 /* install the rounding locks for the new variable and capture it */
571 SCIP_CALL( lockRounding(scip, cons, consdata->intvar) );
572 SCIP_CALL( SCIPcaptureVar(scip, consdata->intvar) );
573
574 /**@todo update LP rows */
575 if( consdata->rows[0] != NULL )
576 {
577 SCIPerrorMessage("cannot change intvar of xor constraint after LP relaxation was created\n");
578 return SCIP_INVALIDCALL;
579 }
580
581 return SCIP_OKAY;
582}
583
584/** adds coefficient to xor constraint */
585static
587 SCIP* scip, /**< SCIP data structure */
588 SCIP_CONS* cons, /**< xor constraint */
589 SCIP_VAR* var /**< variable to add to the constraint */
590 )
591{
592 SCIP_CONSDATA* consdata;
593 SCIP_Bool transformed;
594
595 assert(var != NULL);
596
597 consdata = SCIPconsGetData(cons);
598 assert(consdata != NULL);
599 assert(consdata->rows[0] == NULL);
600
601 /* are we in the transformed problem? */
602 transformed = SCIPconsIsTransformed(cons);
603
604 /* always use transformed variables in transformed constraints */
605 if( transformed )
606 {
607 SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
608 }
609 assert(var != NULL);
610 assert(transformed == SCIPvarIsTransformed(var));
611
612 SCIP_CALL( consdataEnsureVarsSize(scip, consdata, consdata->nvars+1) );
613 consdata->vars[consdata->nvars] = var;
614 consdata->nvars++;
615 consdata->sorted = (consdata->nvars == 1);
616 consdata->changed = TRUE;
617
618 /* install the rounding locks for the new variable */
619 SCIP_CALL( lockRounding(scip, cons, var) );
620
621 /* we only catch this event in presolving stages
622 * we need to catch this event also during exiting presolving because we call applyFixings to clean up the constraint
623 * and this can lead to an insertion of a replacement of variables for which we will try to drop the VARFIXED event.
624 */
627 {
628 SCIP_CONSHDLRDATA* conshdlrdata;
629 SCIP_CONSHDLR* conshdlr;
630
632 assert(conshdlr != NULL);
633 conshdlrdata = SCIPconshdlrGetData(conshdlr);
634 assert(conshdlrdata != NULL);
635
636 SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
637 (SCIP_EVENTDATA*)consdata, NULL) );
638 }
639
640 /**@todo update LP rows */
641 if( consdata->rows[0] != NULL )
642 {
643 SCIPerrorMessage("cannot add coefficients to xor constraint after LP relaxation was created\n");
644 return SCIP_INVALIDCALL;
645 }
646
647 return SCIP_OKAY;
648}
649
650/** deletes coefficient at given position from xor constraint data */
651static
653 SCIP* scip, /**< SCIP data structure */
654 SCIP_CONS* cons, /**< xor constraint */
655 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
656 int pos /**< position of coefficient to delete */
657 )
658{
659 SCIP_CONSDATA* consdata;
660
661 assert(eventhdlr != NULL);
662
663 consdata = SCIPconsGetData(cons);
664 assert(consdata != NULL);
665 assert(0 <= pos && pos < consdata->nvars);
666 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
667
668 /* remove the rounding locks of the deleted variable */
669 SCIP_CALL( unlockRounding(scip, cons, consdata->vars[pos]) );
670
671 /* we only catch this event in presolving stage, so we need to only drop it there */
674 {
675 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_VARFIXED, eventhdlr,
676 (SCIP_EVENTDATA*)consdata, -1) );
677 }
678
679 if( SCIPconsIsTransformed(cons) )
680 {
681 /* if the position is watched, stop watching the position */
682 if( consdata->watchedvar1 == pos )
683 {
684 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar2, -1) );
685 }
686 if( consdata->watchedvar2 == pos )
687 {
688 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, consdata->watchedvar1, -1) );
689 }
690 }
691 assert(pos != consdata->watchedvar1);
692 assert(pos != consdata->watchedvar2);
693
694 /* move the last variable to the free slot */
695 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
696 consdata->nvars--;
697
698 /* if the last variable (that moved) was watched, update the watched position */
699 if( consdata->watchedvar1 == consdata->nvars )
700 consdata->watchedvar1 = pos;
701 if( consdata->watchedvar2 == consdata->nvars )
702 consdata->watchedvar2 = pos;
703
704 consdata->propagated = FALSE;
705 consdata->sorted = FALSE;
706 consdata->changed = TRUE;
707
708 return SCIP_OKAY;
709}
710
711/** sorts and constraint's variables by non-decreasing variable index */
712static
714 SCIP_CONSDATA* consdata /**< constraint data */
715 )
716{
717 assert(consdata != NULL);
718
719 if( !consdata->sorted )
720 {
721 if( consdata->nvars <= 1 )
722 consdata->sorted = TRUE;
723 else
724 {
725 SCIP_VAR* var1 = NULL;
726 SCIP_VAR* var2 = NULL;
727
728 /* remember watch variables */
729 if( consdata->watchedvar1 != -1 )
730 {
731 var1 = consdata->vars[consdata->watchedvar1];
732 assert(var1 != NULL);
733 consdata->watchedvar1 = -1;
734 if( consdata->watchedvar2 != -1 )
735 {
736 var2 = consdata->vars[consdata->watchedvar2];
737 assert(var2 != NULL);
738 consdata->watchedvar2 = -1;
739 }
740 }
741 assert(consdata->watchedvar1 == -1);
742 assert(consdata->watchedvar2 == -1);
743 assert(var1 != NULL || var2 == NULL);
744
745 /* sort variables after index */
746 SCIPsortPtr((void**)consdata->vars, SCIPvarCompActiveAndNegated, consdata->nvars);
747 consdata->sorted = TRUE;
748
749 /* correct watched variables */
750 if( var1 != NULL )
751 {
752 int v;
753
754 /* since negated variables exist, we need to loop over all variables to find the old variable and cannot use
755 * SCIPsortedvecFindPtr()
756 */
757 for( v = consdata->nvars - 1; v >= 0; --v )
758 {
759 if( consdata->vars[v] == var1 )
760 {
761 consdata->watchedvar1 = v;
762 if( var2 == NULL || consdata->watchedvar2 != -1 )
763 break;
764 }
765 else if( consdata->vars[v] == var2 )
766 {
767 assert(consdata->vars[v] != NULL);
768 consdata->watchedvar2 = v;
769 if( consdata->watchedvar1 != -1 )
770 break;
771 }
772 }
773 assert(consdata->watchedvar1 != -1);
774 assert(consdata->watchedvar2 != -1 || var2 == NULL);
775 assert(consdata->watchedvar1 < consdata->nvars);
776 assert(consdata->watchedvar2 < consdata->nvars);
777 }
778 }
779 }
780
781#ifdef SCIP_DEBUG
782 /* check sorting */
783 {
784 int v;
785
786 for( v = 0; v < consdata->nvars; ++v )
787 {
788 assert(v == consdata->nvars-1 || SCIPvarCompareActiveAndNegated(consdata->vars[v], consdata->vars[v+1]) <= 0);
789 }
790 }
791#endif
792}
793
794
795/** gets the key of the given element */
796static
797SCIP_DECL_HASHGETKEY(hashGetKeyXorcons)
798{ /*lint --e{715}*/
799 /* the key is the element itself */
800 return elem;
801}
802
803/** returns TRUE iff both keys are equal; two constraints are equal if they have the same variables */
804static
805SCIP_DECL_HASHKEYEQ(hashKeyEqXorcons)
806{
807 SCIP_CONSDATA* consdata1;
808 SCIP_CONSDATA* consdata2;
809 int i;
810#ifndef NDEBUG
811 SCIP* scip;
812
813 scip = (SCIP*)userptr;
814 assert(scip != NULL);
815#endif
816
817 consdata1 = SCIPconsGetData((SCIP_CONS*)key1);
818 consdata2 = SCIPconsGetData((SCIP_CONS*)key2);
819
820 /* checks trivial case */
821 if( consdata1->nvars != consdata2->nvars )
822 return FALSE;
823
824 /* sorts the constraints */
825 consdataSort(consdata1);
826 consdataSort(consdata2);
827 assert(consdata1->sorted);
828 assert(consdata2->sorted);
829
830 for( i = 0; i < consdata1->nvars ; ++i )
831 {
832 /* tests if variables are equal */
833 if( consdata1->vars[i] != consdata2->vars[i] )
834 {
835 assert(SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == 1 ||
836 SCIPvarCompare(consdata1->vars[i], consdata2->vars[i]) == -1);
837 return FALSE;
838 }
839 assert(SCIPvarCompareActiveAndNegated(consdata1->vars[i], consdata2->vars[i]) == 0);
840 }
841
842 return TRUE;
843}
844
845/** returns the hash value of the key */
846static
847SCIP_DECL_HASHKEYVAL(hashKeyValXorcons)
848{ /*lint --e{715}*/
849 SCIP_CONSDATA* consdata;
850 int minidx;
851 int mididx;
852 int maxidx;
853
854 consdata = SCIPconsGetData((SCIP_CONS*)key);
855 assert(consdata != NULL);
856 assert(consdata->sorted);
857 assert(consdata->nvars > 0);
858
859 /* only active, fixed or negated variables are allowed */
860 assert(consdata->vars[0] != NULL);
861 assert(consdata->vars[consdata->nvars / 2] != NULL);
862 assert(consdata->vars[consdata->nvars - 1] != NULL);
863 assert(SCIPvarIsActive(consdata->vars[0]) || SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_FIXED);
864 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);
865 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);
866
867 minidx = SCIPvarGetIndex(consdata->vars[0]);
868 mididx = SCIPvarGetIndex(consdata->vars[consdata->nvars / 2]);
869 maxidx = SCIPvarGetIndex(consdata->vars[consdata->nvars - 1]);
870 /* note that for all indices it does not hold that they are sorted, because variables are sorted with
871 * SCIPvarCompareActiveAndNegated (see var.c)
872 */
873
874 return SCIPhashFour(consdata->nvars, minidx, mididx, maxidx);
875}
876
877/** deletes all fixed variables and all pairs of equal variables */
878static
880 SCIP* scip, /**< SCIP data structure */
881 SCIP_CONS* cons, /**< xor constraint */
882 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
883 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
884 int* naggrvars, /**< pointer to add up the number of aggregated variables */
885 int* naddconss, /**< pointer to add up the number of added constraints */
886 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
887 )
888{
889 SCIP_CONSDATA* consdata;
890 int v;
891
892 consdata = SCIPconsGetData(cons);
893 assert(consdata != NULL);
894 assert(consdata->nvars == 0 || consdata->vars != NULL);
895 assert(nchgcoefs != NULL);
896
897 SCIPdebugMsg(scip, "before fixings: ");
899
900 v = 0;
901 while( v < consdata->nvars )
902 {
903 SCIP_VAR* var;
904
905 var = consdata->vars[v];
906 assert(SCIPvarIsBinary(var));
907
908 if( SCIPvarGetUbGlobal(var) < 0.5 )
909 {
910 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(var), 0.0));
911 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
912 (*nchgcoefs)++;
913 }
914 else if( SCIPvarGetLbGlobal(var) > 0.5 && consdata->intvar == NULL )
915 {
916 assert(SCIPisEQ(scip, SCIPvarGetUbGlobal(var), 1.0));
917 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
918 consdata->rhs = !consdata->rhs;
919 (*nchgcoefs)++;
920 }
921 else
922 {
923 SCIP_VAR* repvar;
924 SCIP_Bool negated;
925
926 /* get binary representative of variable */
927 SCIP_CALL( SCIPgetBinvarRepresentative(scip, var, &repvar, &negated) );
928
929 /* remove all negations by replacing them with the active variable
930 * it holds that xor(x1, ~x2) = 0 <=> xor(x1, x2) = 1
931 * @note this can only be done if the integer variable does not exist
932 */
933 if( negated && consdata->intvar == NULL )
934 {
935 assert(SCIPvarIsNegated(repvar));
936
937 repvar = SCIPvarGetNegationVar(repvar);
938 consdata->rhs = !consdata->rhs;
939 }
940
941 /* check, if the variable should be replaced with the representative */
942 if( repvar != var )
943 {
944 /* delete old (aggregated) variable */
945 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
946
947 /* add representative instead */
948 SCIP_CALL( addCoef(scip, cons, repvar) );
949 }
950 else
951 ++v;
952 }
953 }
954
955 /* sort the variables in the constraint */
956 consdataSort(consdata);
957 assert(consdata->sorted);
958
959 SCIPdebugMsg(scip, "after sort : ");
961
962 /* delete pairs of equal or negated variables; scan from back to front because deletion doesn't affect the
963 * order of the front variables
964 */
965 v = consdata->nvars-2;
966 while ( v >= 0 )
967 {
968 if( consdata->vars[v] == consdata->vars[v+1] ) /*lint !e679*/
969 {
970 SCIP_VAR* newvars[3];
971 SCIP_Real vals[3];
972
973 newvars[2] = consdata->vars[v];
974 vals[2] = 1.0;
975
976 /* delete both variables */
977 SCIPdebugMsg(scip, "xor constraint <%s>: deleting pair of equal variables <%s>\n",
978 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]));
979 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v+1) );
980 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
981 (*nchgcoefs) += 2;
982 v = MIN(v, consdata->nvars-1);
983
984 /* need to update integer variable, consider the following case:
985 * xor(x1, x2, x3, x4, x5) = 0 (and x1 == x2) was change above to
986 * xor( x3, x4, x5) = 0
987 * assuming we have an integer variable y it needs to be replaced by z with y = x1 + z and
988 * z in [max(lb_y-ub_x1, 0), ub_y-lb_x1]
989 */
990 if( consdata->intvar != NULL )
991 {
992 SCIP_CONS* newcons;
993 SCIP_Real lb;
994 SCIP_Real ub;
995 SCIP_VARTYPE vartype;
996 char varname[SCIP_MAXSTRLEN];
997 char consname[SCIP_MAXSTRLEN];
998
999 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "agg_%s", SCIPvarGetName(consdata->intvar));
1000 lb = MAX(SCIPvarGetLbGlobal(consdata->intvar) - SCIPvarGetUbGlobal(newvars[2]), 0); /*lint !e666*/
1001 ub = MAX(SCIPvarGetUbGlobal(consdata->intvar) - SCIPvarGetLbGlobal(newvars[2]), 0); /*lint !e666*/
1002 vartype = SCIPvarGetType(consdata->intvar);
1003
1004 SCIP_CALL( SCIPcreateVar(scip, &newvars[0], varname, lb, ub, 0.0, vartype,
1005 SCIPvarIsInitial(consdata->intvar), SCIPvarIsRemovable(consdata->intvar),
1006 NULL, NULL, NULL, NULL, NULL) );
1007 SCIP_CALL( SCIPaddVar(scip, newvars[0]) );
1008 vals[0] = 1.0;
1009
1010 newvars[1] = consdata->intvar;
1011 vals[1] = -1.0;
1012
1013 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons));
1014
1015 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 3, newvars, vals, 0.0, 0.0,
1016 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), TRUE, /*SCIPconsIsEnforced(cons),*/
1017 TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
1020
1021 SCIP_CALL( SCIPaddCons(scip, newcons) );
1022 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1023 ++(*naddconss);
1024
1025 SCIP_CALL( setIntvar(scip, cons, newvars[0]) );
1026 SCIP_CALL( SCIPreleaseVar(scip, &newvars[0]) );
1027 }
1028 }
1029 else if( consdata->vars[v] == SCIPvarGetNegatedVar(consdata->vars[v+1]) ) /*lint !e679*/
1030 {
1031 /* delete both variables and negate the rhs */
1032 SCIPdebugMsg(scip, "xor constraint <%s>: deleting pair of negated variables <%s> and <%s>\n",
1033 SCIPconsGetName(cons), SCIPvarGetName(consdata->vars[v]), SCIPvarGetName(consdata->vars[v+1])); /*lint !e679*/
1034 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v+1) );
1035 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1036 (*nchgcoefs) += 2;
1037 consdata->rhs = !consdata->rhs;
1038 v = MIN(v, consdata->nvars-1);
1039
1040 /* need to update integer variable, consider the following case:
1041 * xor(x1, x2, x3, x4, x5) = 0 (and x1 = ~x2) was change above to
1042 * xor( x3, x4, x5) = 1
1043 * 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]
1044 */
1045 if( consdata->rhs && consdata->intvar != NULL )
1046 {
1047 SCIP_VAR* newvar;
1048 SCIP_Real lb;
1049 SCIP_Real ub;
1050 SCIP_VARTYPE vartype;
1051 char varname[SCIP_MAXSTRLEN];
1052 SCIP_Bool aggregated;
1053 SCIP_Bool infeasible;
1054 SCIP_Bool redundant;
1055
1056 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "agg_%s", SCIPvarGetName(consdata->intvar));
1057 /* avoid infeasible cutoffs and guarantee non-negative bounds for the new artificial integer variable */
1058 lb = MAX(SCIPvarGetLbGlobal(consdata->intvar) - 1, 0); /*lint !e666*/
1059 ub = MAX(SCIPvarGetUbGlobal(consdata->intvar) - 1, 0); /*lint !e666*/
1060 vartype = (lb == 0 && ub == 1) ? SCIP_VARTYPE_BINARY : SCIPvarGetType(consdata->intvar);
1061
1062 SCIP_CALL( SCIPcreateVar(scip, &newvar, varname, lb, ub, 0.0, vartype,
1063 SCIPvarIsInitial(consdata->intvar), SCIPvarIsRemovable(consdata->intvar),
1064 NULL, NULL, NULL, NULL, NULL) );
1065 SCIP_CALL( SCIPaddVar(scip, newvar) );
1066
1067 SCIP_CALL( SCIPaggregateVars(scip, consdata->intvar, newvar, 1.0, -1.0, 1.0, &infeasible, &redundant, &aggregated) );
1068 assert(infeasible || redundant || SCIPdoNotAggr(scip));
1069
1070 if( infeasible )
1071 {
1072 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
1073 *cutoff = TRUE;
1074 break;
1075 }
1076
1077 if( aggregated )
1078 {
1079 (*naggrvars)++;
1080
1081 if( SCIPvarIsActive(newvar) )
1082 {
1083 SCIP_CALL( setIntvar(scip, cons, newvar) );
1084 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
1085 }
1086 /* the new variable should only by inactive if it was fixed due to the aggregation, so also the old variable
1087 * should be fixed now.
1088 *
1089 * @todo if newvar is not active we may want to transform the xor into a linear constraint
1090 */
1091 else
1092 {
1093 assert(SCIPvarGetStatus(newvar) == SCIP_VARSTATUS_FIXED);
1094 assert(SCIPisEQ(scip, SCIPvarGetLbGlobal(consdata->intvar), SCIPvarGetUbGlobal(consdata->intvar)));
1095
1096 SCIP_CALL( setIntvar(scip, cons, newvar) );
1097 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
1098 }
1099 }
1100 else
1101 {
1102 SCIP_CONS* newcons;
1103 char consname[SCIP_MAXSTRLEN];
1104 SCIP_VAR* newvars[2];
1105 SCIP_Real vals[2];
1106
1107 newvars[0] = consdata->intvar;
1108 vals[0] = 1.0;
1109 newvars[1] = newvar;
1110 vals[1] = -1.0;
1111
1112 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons));
1113
1114 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, newvars, vals, 1.0, 1.0,
1115 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), TRUE, /*SCIPconsIsEnforced(cons),*/
1116 TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
1119
1120 SCIP_CALL( SCIPaddCons(scip, newcons) );
1121 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1122 ++(*naddconss);
1123
1124 SCIP_CALL( setIntvar(scip, cons, newvar) );
1125 SCIP_CALL( SCIPreleaseVar(scip, &newvar) );
1126 }
1127 }
1128 }
1129 else
1130 assert(SCIPvarGetProbvar(consdata->vars[v]) != SCIPvarGetProbvar(consdata->vars[v+1])); /*lint !e679*/
1131 --v;
1132 }
1133
1134 SCIPdebugMsg(scip, "after fixings : ");
1135 SCIPdebug( SCIP_CALL(consdataPrint(scip, consdata, NULL, TRUE)) );
1136
1137 return SCIP_OKAY;
1138}
1139
1140/** adds extended flow formulation
1141 *
1142 * The extended flow formulation is built as follows: Let \f$x_1, \dots, x_k\f$ be the variables contained in the given
1143 * XOR constraint. We construct a two layered flow network. The upper layer is called the north layer and the lower is
1144 * 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
1145 * (denoted by 'nn' and 'ss', respectively), as well as arcs that change the layers (denoted by 'ns' and 'sn'). For
1146 * \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
1147 * \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
1148 * located on the north or south layer. A change in the layers corresponds to a parity change, i.e., the corresponding
1149 * variable \f$x_i\f$ is 1 (and 0 otherwise).
1150 */
1151static
1153 SCIP* scip, /**< SCIP data structure */
1154 SCIP_CONS* cons, /**< constraint to check */
1155 int* naggrvars, /**< pointer to add up the number of aggregated variables */
1156 int* naddedconss /**< number of added constraints */
1157 )
1158{
1159 char name[SCIP_MAXSTRLEN];
1160 SCIP_CONSDATA* consdata;
1161 SCIP_VAR* varprevnn = NULL;
1162 SCIP_VAR* varprevns = NULL;
1163 SCIP_VAR* varprevsn = NULL;
1164 SCIP_VAR* varprevss = NULL;
1165 SCIP_VAR* vars[4];
1166 SCIP_Real vals[4];
1167 int i;
1168
1169 assert( scip != NULL );
1170 assert( cons != NULL );
1171 assert( naddedconss != NULL );
1172 *naddedconss = 0;
1173
1174 /* exit if contraints is modifiable */
1175 if ( SCIPconsIsModifiable(cons) )
1176 return SCIP_OKAY;
1177
1178 consdata = SCIPconsGetData(cons);
1179 assert( consdata != NULL );
1180
1181 /* exit if extended formulation has been added already */
1182 if ( consdata->extvars != NULL )
1183 return SCIP_OKAY;
1184
1185 /* xor constraints with at most 3 variables are handled directly through rows for the convex hull */
1186 if ( consdata->nvars <= 3 )
1187 return SCIP_OKAY;
1188
1189 SCIPdebugMsg(scip, "Add extended formulation for xor constraint <%s> ...\n", SCIPconsGetName(cons));
1190 assert( consdata->extvars == NULL );
1191 assert( consdata->nextvars == 0 );
1192 assert( consdata->extvarssize == 0 );
1193
1194 /* get storage for auxiliary variables */
1195 consdata->extvarssize = 4 * (consdata->nvars);
1196 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->extvars), consdata->extvarssize) );
1197
1198 /* pass through components */
1199 for (i = 0; i < consdata->nvars; ++i)
1200 {
1201 /* variables: n - north, s - south */
1202 SCIP_VAR* varnn = NULL;
1203 SCIP_VAR* varns = NULL;
1204 SCIP_VAR* varsn = NULL;
1205 SCIP_VAR* varss = NULL;
1206 SCIP_CONS* newcons;
1207 SCIP_Real rhs = 0.0;
1208 SCIP_Bool infeasible = FALSE;
1209 SCIP_Bool redundant = FALSE;
1210 SCIP_Bool aggregated = FALSE;
1211 int cnt = 0;
1212
1213 /* create variables */
1214 if ( i == 0 )
1215 {
1216 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1217 SCIP_CALL( SCIPcreateVar(scip, &varnn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1218 SCIP_CALL( SCIPaddVar(scip, varnn) );
1219
1220 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1221 SCIP_CALL( SCIPcreateVar(scip, &varns, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1222 SCIP_CALL( SCIPaddVar(scip, varns) );
1223
1224 /* need to lock variables, because we aggregate them */
1225 SCIP_CALL( SCIPlockVarCons(scip, varnn, cons, TRUE, TRUE) );
1226 SCIP_CALL( SCIPlockVarCons(scip, varns, cons, TRUE, TRUE) );
1227
1228 /* aggregate ns variable with original variable */
1229 SCIP_CALL( SCIPaggregateVars(scip, varns, consdata->vars[0], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1230 assert( ! infeasible );
1231 assert( redundant );
1232 assert( aggregated );
1233 ++(*naggrvars);
1234 }
1235 else
1236 {
1237 if ( i == consdata->nvars-1 )
1238 {
1239 if ( consdata->rhs )
1240 {
1241 /* if the rhs is 1 (true) the flow goes to the bottom level */
1242 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1243 SCIP_CALL( SCIPcreateVar(scip, &varns, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1244 SCIP_CALL( SCIPaddVar(scip, varns) );
1245
1246 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ss", SCIPconsGetName(cons), i);
1247 SCIP_CALL( SCIPcreateVar(scip, &varss, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1248 SCIP_CALL( SCIPaddVar(scip, varss) );
1249
1250 /* need to lock variables, because we aggregate them */
1251 SCIP_CALL( SCIPlockVarCons(scip, varns, cons, TRUE, TRUE) );
1252 SCIP_CALL( SCIPlockVarCons(scip, varss, cons, TRUE, TRUE) );
1253
1254 /* aggregate ns variable with original variable */
1255 SCIP_CALL( SCIPaggregateVars(scip, varns, consdata->vars[i], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1256 assert( ! infeasible );
1257 assert( redundant );
1258 assert( aggregated );
1259 ++(*naggrvars);
1260 }
1261 else
1262 {
1263 /* if the rhs is 0 (false) the flow stays on the top level */
1264 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1265 SCIP_CALL( SCIPcreateVar(scip, &varnn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1266 SCIP_CALL( SCIPaddVar(scip, varnn) );
1267
1268 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_sn", SCIPconsGetName(cons), i);
1269 SCIP_CALL( SCIPcreateVar(scip, &varsn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1270 SCIP_CALL( SCIPaddVar(scip, varsn) );
1271
1272 /* need to lock variables, because we aggregate them */
1273 SCIP_CALL( SCIPlockVarCons(scip, varnn, cons, TRUE, TRUE) );
1274 SCIP_CALL( SCIPlockVarCons(scip, varsn, cons, TRUE, TRUE) );
1275
1276 /* aggregate sn variable with original variable */
1277 SCIP_CALL( SCIPaggregateVars(scip, varsn, consdata->vars[i], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1278 assert( ! infeasible );
1279 assert( redundant );
1280 assert( aggregated );
1281 ++(*naggrvars);
1282 }
1283 }
1284 else
1285 {
1286 /* add the four flow variables */
1287 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_nn", SCIPconsGetName(cons), i);
1288 SCIP_CALL( SCIPcreateVar(scip, &varnn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1289 SCIP_CALL( SCIPaddVar(scip, varnn) );
1290
1291 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ns", SCIPconsGetName(cons), i);
1292 SCIP_CALL( SCIPcreateVar(scip, &varns, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1293 SCIP_CALL( SCIPaddVar(scip, varns) );
1294
1295 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_sn", SCIPconsGetName(cons), i);
1296 SCIP_CALL( SCIPcreateVar(scip, &varsn, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1297 SCIP_CALL( SCIPaddVar(scip, varsn) );
1298
1299 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_ss", SCIPconsGetName(cons), i);
1300 SCIP_CALL( SCIPcreateVar(scip, &varss, name, 0.0, 1.0, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1301 SCIP_CALL( SCIPaddVar(scip, varss) );
1302
1303 SCIP_CALL( SCIPlockVarCons(scip, varnn, cons, TRUE, TRUE) );
1304 SCIP_CALL( SCIPlockVarCons(scip, varns, cons, TRUE, TRUE) );
1305 SCIP_CALL( SCIPlockVarCons(scip, varsn, cons, TRUE, TRUE) );
1306 SCIP_CALL( SCIPlockVarCons(scip, varss, cons, TRUE, TRUE) );
1307
1308 /* add coupling constraint */
1309 cnt = 0;
1310 if ( varns != NULL )
1311 {
1312 vars[cnt] = varns;
1313 vals[cnt++] = 1.0;
1314 }
1315 if ( varsn != NULL )
1316 {
1317 vars[cnt] = varsn;
1318 vals[cnt++] = 1.0;
1319 }
1320 assert( SCIPvarIsTransformed(consdata->vars[i]) );
1321 vars[cnt] = consdata->vars[i];
1322 vals[cnt++] = -1.0;
1323
1324 assert( cnt >= 2 );
1325 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_couple", SCIPconsGetName(cons));
1326 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1327 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, 0.0, 0.0,
1329 SCIP_CALL( SCIPaddCons(scip, newcons) );
1330 SCIPdebugPrintCons(scip, newcons, NULL);
1331 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1332 ++(*naddedconss);
1333 }
1334
1335 /* add south flow conservation constraint */
1336
1337 /* incoming variables */
1338 cnt = 0;
1339 if ( varprevss != NULL )
1340 {
1341 vars[cnt] = varprevss;
1342 vals[cnt++] = 1.0;
1343 }
1344 if ( varprevns != NULL )
1345 {
1346 vars[cnt] = varprevns;
1347 vals[cnt++] = 1.0;
1348 }
1349
1350 /* outgoing variables */
1351 if ( varss != NULL )
1352 {
1353 vars[cnt] = varss;
1354 vals[cnt++] = -1.0;
1355 }
1356 if ( varsn != NULL )
1357 {
1358 vars[cnt] = varsn;
1359 vals[cnt++] = -1.0;
1360 }
1361
1362 assert( cnt >= 2 );
1363 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_south", SCIPconsGetName(cons));
1364 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1365 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, 0.0, 0.0,
1367 SCIP_CALL( SCIPaddCons(scip, newcons) );
1368 SCIPdebugPrintCons(scip, newcons, NULL);
1369 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1370 ++(*naddedconss);
1371 }
1372
1373 /* add north flow conservation constraint */
1374
1375 /* incoming variables */
1376 cnt = 0;
1377 if ( varprevnn != NULL )
1378 {
1379 vars[cnt] = varprevnn;
1380 vals[cnt++] = 1.0;
1381 }
1382 if ( varprevsn != NULL )
1383 {
1384 vars[cnt] = varprevsn;
1385 vals[cnt++] = 1.0;
1386 }
1387
1388 /* outgoing variables */
1389 if ( varnn != NULL )
1390 {
1391 vars[cnt] = varnn;
1392 vals[cnt++] = -1.0;
1393 }
1394 if ( varns != NULL )
1395 {
1396 vars[cnt] = varns;
1397 vals[cnt++] = -1.0;
1398 }
1399
1400 assert( cnt >= 2 );
1401 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_north", SCIPconsGetName(cons));
1402 if ( i == 0 )
1403 rhs = -1.0;
1404 else
1405 rhs = 0.0;
1406
1407 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1408 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, cnt, vars, vals, rhs, rhs,
1410 SCIP_CALL( SCIPaddCons(scip, newcons) );
1411 SCIPdebugPrintCons(scip, newcons, NULL);
1412 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1413 ++(*naddedconss);
1414
1415 /* store variables */
1416 consdata->extvars[4*i] = varnn; /*lint !e679*/
1417 consdata->extvars[4*i + 1] = varns; /*lint !e679*/
1418 consdata->extvars[4*i + 2] = varsn; /*lint !e679*/
1419 consdata->extvars[4*i + 3] = varss; /*lint !e679*/
1420
1421 if ( varnn != NULL )
1422 ++(consdata->nextvars);
1423 if ( varns != NULL )
1424 ++(consdata->nextvars);
1425 if ( varsn != NULL )
1426 ++(consdata->nextvars);
1427 if ( varss != NULL )
1428 ++(consdata->nextvars);
1429
1430 /* store previous variables */
1431 varprevnn = varnn;
1432 varprevns = varns;
1433 varprevsn = varsn;
1434 varprevss = varss;
1435 }
1436
1437 return SCIP_OKAY;
1438}
1439
1440/** adds extended asymmetric formulation
1441 *
1442 * The extended asymmetric formulation is constructed as follows: Let \f$x_1, \dots, x_k\f$ be the variables contained
1443 * in the given XOR constraint. We introduce variables \f$p_1, \ldots, p_k\f$ with the following constraints: \f$p_1 =
1444 * x_1\f$, \f$p_k = 1\f$, and for \f$i = 2, \ldots, k-1\f$:
1445 * \f[
1446 * \begin{array}{ll}
1447 * p_i & \leq p_{i-1} + x_i\\
1448 * p_i & \leq 2 - (p_{i-1} + x_i)\\
1449 * p_i & \geq p_{i-1} - x_i\\
1450 * p_i & \geq x_i - p_{i-1}.
1451 * \end{array}
1452 * \f]
1453 * This formulation is described in
1454 *
1455 * Robert D. Carr and Goran Konjevod@n
1456 * Polyhedral combinatorics@n
1457 * In Harvey Greenberg, editor, Tutorials on emerging methodologies and applications in Operations Research,@n
1458 * Chapter 2, pages (2-1)-(2-48). Springer, 2004.
1459 */
1460static
1462 SCIP* scip, /**< SCIP data structure */
1463 SCIP_CONS* cons, /**< constraint to check */
1464 int* naggrvars, /**< pointer to add up the number of aggregated variables */
1465 int* naddedconss /**< number of added constraints */
1466 )
1467{
1468 char name[SCIP_MAXSTRLEN];
1469 SCIP_CONSDATA* consdata;
1470 SCIP_VAR* vars[3];
1471 SCIP_Real vals[3];
1472 SCIP_VAR* prevvar = NULL;
1473 int i;
1474
1475 assert( scip != NULL );
1476 assert( cons != NULL );
1477 assert( naddedconss != NULL );
1478 *naddedconss = 0;
1479
1480 /* exit if contraints is modifiable */
1481 if ( SCIPconsIsModifiable(cons) )
1482 return SCIP_OKAY;
1483
1484 consdata = SCIPconsGetData(cons);
1485 assert( consdata != NULL );
1486
1487 /* exit if extended formulation has been added already */
1488 if ( consdata->extvars != NULL )
1489 return SCIP_OKAY;
1490
1491 /* xor constraints with at most 3 variables are handled directly through rows for the convex hull */
1492 if ( consdata->nvars <= 3 )
1493 return SCIP_OKAY;
1494
1495 SCIPdebugMsg(scip, "Add extended formulation for xor constraint <%s> ...\n", SCIPconsGetName(cons));
1496 assert( consdata->extvars == NULL );
1497 assert( consdata->nextvars == 0 );
1498
1499 /* get storage for auxiliary variables */
1500 consdata->extvarssize = consdata->nvars;
1501 consdata->nextvars = consdata->nvars;
1502 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(consdata->extvars), consdata->extvarssize ) );
1503
1504 /* pass through components */
1505 for (i = 0; i < consdata->nvars; ++i)
1506 {
1507 SCIP_Bool infeasible = FALSE;
1508 SCIP_Bool redundant = FALSE;
1509 SCIP_Bool aggregated = FALSE;
1510 SCIP_CONS* newcons;
1511 SCIP_VAR* artvar = NULL;
1512 SCIP_Real lb = 0.0;
1513 SCIP_Real ub = 1.0;
1514
1515 /* determine fixing for last variables */
1516 if ( i == consdata->nvars-1 )
1517 {
1518 if ( consdata->rhs )
1519 {
1520 lb = 1.0;
1521 ub = 1.0;
1522 }
1523 else
1524 {
1525 lb = 0.0;
1526 ub = 0.0;
1527 }
1528 }
1529
1530 /* create variable */
1531 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "p_%s_%d", SCIPconsGetName(cons), i);
1532 SCIP_CALL( SCIPcreateVar(scip, &artvar, name, lb, ub, 0.0, SCIP_VARTYPE_IMPLINT, SCIPconsIsInitial(cons), SCIPconsIsRemovable(cons), NULL, NULL, NULL, NULL, NULL) );
1533 SCIP_CALL( SCIPaddVar(scip, artvar) );
1534 SCIP_CALL( SCIPlockVarCons(scip, artvar, cons, TRUE, TRUE) );
1535
1536 /* create constraints */
1537 if ( i == 0 )
1538 {
1539 /* aggregate artificial variable with original variable */
1540 SCIP_CALL( SCIPaggregateVars(scip, artvar, consdata->vars[0], 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
1541 assert( ! infeasible );
1542 assert( redundant );
1543 assert( aggregated );
1544 ++(*naggrvars);
1545 }
1546 else
1547 {
1548 assert( SCIPvarIsTransformed(consdata->vars[i]) );
1549
1550 /* add first constraint */
1551 vars[0] = artvar;
1552 vals[0] = 1.0;
1553 vars[1] = prevvar;
1554 vals[1] = -1.0;
1555 vars[2] = consdata->vars[i];
1556 vals[2] = -1.0;
1557
1558 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_1", SCIPconsGetName(cons), i);
1559 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1560 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1562 SCIP_CALL( SCIPaddCons(scip, newcons) );
1563 SCIPdebugPrintCons(scip, newcons, NULL);
1564 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1565 ++(*naddedconss);
1566
1567 /* add second constraint */
1568 vars[0] = artvar;
1569 vals[0] = 1.0;
1570 vars[1] = prevvar;
1571 vals[1] = 1.0;
1572 vars[2] = consdata->vars[i];
1573 vals[2] = 1.0;
1574
1575 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_2", SCIPconsGetName(cons), i);
1576 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1577 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 2.0,
1579 SCIP_CALL( SCIPaddCons(scip, newcons) );
1580 SCIPdebugPrintCons(scip, newcons, NULL);
1581 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1582 ++(*naddedconss);
1583
1584 /* add third constraint */
1585 vars[0] = artvar;
1586 vals[0] = -1.0;
1587 vars[1] = prevvar;
1588 vals[1] = 1.0;
1589 vars[2] = consdata->vars[i];
1590 vals[2] = -1.0;
1591
1592 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_3", SCIPconsGetName(cons), i);
1593 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1594 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1596 SCIP_CALL( SCIPaddCons(scip, newcons) );
1597 SCIPdebugPrintCons(scip, newcons, NULL);
1598 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1599 ++(*naddedconss);
1600
1601 /* add fourth constraint */
1602 vars[0] = artvar;
1603 vals[0] = -1.0;
1604 vars[1] = prevvar;
1605 vals[1] = -1.0;
1606 vars[2] = consdata->vars[i];
1607 vals[2] = 1.0;
1608
1609 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_%d_4", SCIPconsGetName(cons), i);
1610 /* not initial, separate, do not enforce, do not check, propagate, not local, not modifiable, dynamic, removable, not sticking */
1611 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, name, 3, vars, vals, -SCIPinfinity(scip), 0.0,
1613 SCIP_CALL( SCIPaddCons(scip, newcons) );
1614 SCIPdebugPrintCons(scip, newcons, NULL);
1615 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1616 ++(*naddedconss);
1617 }
1618
1619 /* store variable */
1620 consdata->extvars[i] = artvar;
1621 prevvar = artvar;
1622 }
1623
1624 return SCIP_OKAY;
1625}
1626
1627/** creates LP row corresponding to xor constraint:
1628 * x1 + ... + xn - 2q == rhs
1629 * with internal integer variable q;
1630 * in the special case of 3 variables and c = 0, the following linear system is created:
1631 * + x - y - z <= 0
1632 * - x + y - z <= 0
1633 * - x - y + z <= 0
1634 * + x + y + z <= 2
1635 * in the special case of 3 variables and c = 1, the following linear system is created:
1636 * - x + y + z <= 1
1637 * + x - y + z <= 1
1638 * + x + y - z <= 1
1639 * - x - y - z <= -1
1640 */
1641static
1643 SCIP* scip, /**< SCIP data structure */
1644 SCIP_CONS* cons /**< constraint to check */
1645 )
1646{
1647 SCIP_CONSDATA* consdata;
1648 char varname[SCIP_MAXSTRLEN];
1649
1650 consdata = SCIPconsGetData(cons);
1651 assert(consdata != NULL);
1652 assert(consdata->rows[0] == NULL);
1653
1654 if( SCIPconsIsModifiable(cons) || consdata->nvars != 3 )
1655 {
1656 SCIP_Real rhsval;
1657
1658 /* create internal variable, if not yet existing */
1659 if( consdata->intvar == NULL )
1660 {
1661 int ub;
1662
1663 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "XOR_artificial_%s_int", SCIPconsGetName(cons));
1664 ub = consdata->nvars/2;
1665 SCIP_CALL( SCIPcreateVar(scip, &consdata->intvar, varname, 0.0, (SCIP_Real)ub, 0.0,
1666 consdata->nvars >= 4 ? SCIP_VARTYPE_INTEGER : SCIP_VARTYPE_BINARY,
1668 SCIP_CALL( SCIPaddVar(scip, consdata->intvar) );
1669
1670#ifdef WITH_DEBUG_SOLUTION
1671 if( SCIPdebugIsMainscip(scip) )
1672 {
1673 SCIP_Real solval;
1674 int count = 0;
1675 int v;
1676
1677 for( v = consdata->nvars - 1; v >= 0; --v )
1678 {
1679 SCIP_CALL( SCIPdebugGetSolVal(scip, consdata->vars[v], &solval) );
1680 count += (solval > 0.5 ? 1 : 0);
1681 }
1682 assert((count - consdata->rhs) % 2 == 0);
1683 solval = (SCIP_Real) ((count - consdata->rhs) / 2);
1684
1685 /* store debug sol value of artificial integer variable */
1686 SCIP_CALL( SCIPdebugAddSolVal(scip, consdata->intvar, solval) );
1687 }
1688#endif
1689
1690 /* install the rounding locks for the internal variable */
1691 SCIP_CALL( lockRounding(scip, cons, consdata->intvar) );
1692 }
1693
1694 /* create LP row */
1695 rhsval = (consdata->rhs ? 1.0 : 0.0);
1696 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[0], cons, SCIPconsGetName(cons), rhsval, rhsval,
1698 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[0], consdata->intvar, -2.0) );
1699 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[0], consdata->nvars, consdata->vars, 1.0) );
1700 }
1701 else if( !consdata->rhs )
1702 {
1703 char rowname[SCIP_MAXSTRLEN];
1704 int r;
1705
1706 /* create the <= 0 rows with one positive sign */
1707 for( r = 0; r < 3; ++r )
1708 {
1709 int v;
1710
1711 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), r);
1712 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[r], cons, rowname, -SCIPinfinity(scip), 0.0,
1714 for( v = 0; v < 3; ++v )
1715 {
1716 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[r], consdata->vars[v], v == r ? +1.0 : -1.0) );
1717 }
1718 }
1719
1720 /* create the <= 2 row with all positive signs */
1721 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_3", SCIPconsGetName(cons));
1722 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[3], cons, rowname, -SCIPinfinity(scip), 2.0,
1724 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[3], consdata->nvars, consdata->vars, 1.0) );
1725
1726 /* create extra LP row if integer variable exists */
1727 if( consdata->intvar != NULL )
1728 {
1729 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[4], cons, SCIPconsGetName(cons), 0.0, 0.0,
1731 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[4], consdata->intvar, -2.0) );
1732 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[4], consdata->nvars, consdata->vars, 1.0) );
1733 }
1734 }
1735 else
1736 {
1737 char rowname[SCIP_MAXSTRLEN];
1738 int r;
1739
1740 /* create the <= 1 rows with one negative sign */
1741 for( r = 0; r < 3; ++r )
1742 {
1743 int v;
1744
1745 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_%d", SCIPconsGetName(cons), r);
1746 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[r], cons, rowname, -SCIPinfinity(scip), 1.0,
1748 for( v = 0; v < 3; ++v )
1749 {
1750 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[r], consdata->vars[v], v == r ? -1.0 : +1.0) );
1751 }
1752 }
1753
1754 /* create the <= -1 row with all negative signs */
1755 (void) SCIPsnprintf(rowname, SCIP_MAXSTRLEN, "%s_3", SCIPconsGetName(cons));
1756 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[3], cons, rowname, -SCIPinfinity(scip), -1.0,
1758 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[3], consdata->nvars, consdata->vars, -1.0) );
1759
1760 /* create extra LP row if integer variable exists */
1761 if( consdata->intvar != NULL )
1762 {
1763 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &consdata->rows[4], cons, SCIPconsGetName(cons), 1.0, 1.0,
1765 SCIP_CALL( SCIPaddVarToRow(scip, consdata->rows[4], consdata->intvar, -2.0) );
1766 SCIP_CALL( SCIPaddVarsToRowSameCoef(scip, consdata->rows[4], consdata->nvars, consdata->vars, 1.0) );
1767 }
1768 }
1769
1770 return SCIP_OKAY;
1771}
1772
1773/** adds linear relaxation of or constraint to the LP */
1774static
1776 SCIP* scip, /**< SCIP data structure */
1777 SCIP_CONS* cons, /**< constraint to check */
1778 SCIP_Bool* infeasible /**< pointer to store whether infeasibility was detected */
1779 )
1780{
1781 SCIP_CONSDATA* consdata;
1782 int r;
1783
1784 consdata = SCIPconsGetData(cons);
1785 assert(consdata != NULL);
1786 assert(infeasible != NULL);
1787 assert(!(*infeasible));
1788
1789 if( consdata->rows[0] == NULL )
1790 {
1792 }
1793 assert(consdata->rows[0] != NULL);
1794 for( r = 0; r < NROWS && !(*infeasible); ++r )
1795 {
1796 if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1797 {
1798 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, infeasible) );
1799 }
1800 }
1801
1802 return SCIP_OKAY;
1803}
1804
1805/** returns whether all rows of the LP relaxation are in the current LP */
1806static
1808 SCIP_CONSDATA* consdata /**< constraint data */
1809 )
1810{
1811 assert(consdata != NULL);
1812
1813 if( consdata->rows[0] == NULL ) /* LP relaxation does not exist */
1814 return FALSE;
1815 else
1816 {
1817 int r;
1818 for( r = 0; r < NROWS; ++r )
1819 {
1820 if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
1821 return FALSE;
1822 }
1823 return TRUE;
1824 }
1825}
1826
1827/** checks xor constraint for feasibility of given solution: returns TRUE iff constraint is feasible */
1828static
1830 SCIP* scip, /**< SCIP data structure */
1831 SCIP_CONS* cons, /**< constraint to check */
1832 SCIP_SOL* sol, /**< solution to check, NULL for current solution */
1833 SCIP_Bool checklprows, /**< Do constraints represented by rows in the current LP have to be checked? */
1834 SCIP_Bool printreason, /**< Should the reason for the violation be printed? */
1835 SCIP_Bool* violated /**< pointer to store whether the constraint is violated */
1836 )
1837{
1838 SCIP_CONSDATA* consdata;
1839
1840 assert(violated != NULL);
1841
1842 consdata = SCIPconsGetData(cons);
1843 assert(consdata != NULL);
1844
1845 *violated = FALSE;
1846
1847 /* check feasibility of constraint if necessary */
1848 if( checklprows || !allRowsInLP(consdata) )
1849 {
1850 SCIP_Real maxcenval = 0.0;
1851 SCIP_Real sumcenval = 0.0;
1852 SCIP_Real sumsolval = 0.0;
1853 SCIP_Real cenval;
1854 SCIP_Real solval;
1855 SCIP_Real viol;
1856 SCIP_Bool odd = consdata->rhs;
1857 int ones = 0;
1858 int i;
1859
1860 /* increase age of constraint; age is reset to zero, if a violation was found only in case we are in
1861 * enforcement
1862 */
1863 if( sol == NULL )
1864 {
1865 SCIP_CALL( SCIPincConsAge(scip, cons) );
1866 }
1867
1868 /* evaluate operator variables */
1869 for( i = 0; i < consdata->nvars; ++i )
1870 {
1871 solval = SCIPgetSolVal(scip, sol, consdata->vars[i]);
1872
1873 if( solval > 0.5 )
1874 {
1875 odd = !odd;
1876 ++ones;
1877 cenval = 1.0 - solval;
1878 }
1879 else
1880 cenval = solval;
1881
1882 if( maxcenval < cenval )
1883 maxcenval = cenval;
1884
1885 sumcenval += cenval;
1886 sumsolval += solval;
1887 }
1888
1889 /* the center value sum is the additive distance to the nearest integral solution infeasible if odd
1890 * and otherwise the additive distance to the next nearest integral solution infeasible must be at least one
1891 * see separateCons() for further intuition
1892 */
1893 viol = MAX(0.0, (odd ? 1.0 : 2.0 * maxcenval) - sumcenval);
1894
1895 /* additionally check linear feasibility of an existing integer variable */
1896 if( consdata->intvar != NULL )
1897 {
1898 solval = REALABS(sumsolval - 2 * SCIPgetSolVal(scip, sol, consdata->intvar) - (SCIP_Real)consdata->rhs);
1899
1900 if( viol < solval )
1901 viol = solval;
1902 }
1903
1904 if( SCIPisFeasPositive(scip, viol) )
1905 {
1906 *violated = TRUE;
1907
1908 /* only reset constraint age if we are in enforcement */
1909 if( sol == NULL )
1910 {
1912 }
1913
1914 if( printreason )
1915 {
1916 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
1917 SCIPinfoMessage(scip, NULL, ";\n");
1918 SCIPinfoMessage(scip, NULL, "violation: %d operands are set to TRUE ", ones);
1919
1920 if( consdata->intvar == NULL )
1921 SCIPinfoMessage(scip, NULL, "and all sum up to %g\n", sumsolval);
1922 else
1923 SCIPinfoMessage(scip, NULL, "but integer variable is %g\n", SCIPgetSolVal(scip, sol, consdata->intvar));
1924 }
1925 }
1926
1927 /* update constraint violation in solution */
1928 if( sol != NULL )
1929 SCIPupdateSolConsViolation(scip, sol, viol, viol);
1930 }
1931
1932 return SCIP_OKAY;
1933}
1934
1935/** separates current LP solution
1936 *
1937 * Consider a XOR-constraint
1938 * \f[
1939 * x_1 \oplus x_2 \oplus \dots \oplus x_n = b
1940 * \f]
1941 * 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
1942 * inequalities of the convex hull.
1943 *
1944 * The separation of larger XOR constraints has been described by @n
1945 * Xiaojie Zhang and Paul H. Siegel@n
1946 * "Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes"@n
1947 * IEEE Transactions on Information Theory, vol. 58, no. 10, 2012
1948 *
1949 * We separate the inequalities
1950 * \f[
1951 * \sum_{j \in S} (1 - x_j) + \sum_{j \notin S} x_j \geq 1
1952 * \f]
1953 * with \f$|S| \equiv (b+1) \mbox{ mod } 2\f$ as follows. That these inequalities are valid can be seen as follows: Let
1954 * \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
1955 * all \f$j \in S\f$ and \f$x_j = 0\f$ for all \f$j \notin S\f$. Thus we should have
1956 * \f[
1957 * \oplus_{j \in S} x_j = |S| \mbox{ mod } 2 = b+1 \mbox{ mod } 2,
1958 * \f]
1959 * which is not equal to \f$b\f$ as required by the XOR-constraint.
1960 *
1961 * 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
1962 * \f[
1963 * \sum_{j \in L} (1 - x_j) + \sum_{j \notin L} x_j \geq 1
1964 * \f]
1965 * is the only inequality that can be violated. We rewrite the inequality as
1966 * \f[
1967 * \sum_{j \in L} x_j - \sum_{j \notin L} x_j \leq |L| - 1.
1968 * \f]
1969 * These inequalities are added.
1970 *
1971 * Otherwise let \f$k = \mbox{argmin}\{x^*_j \;:\; j \in L\}\f$ and check the inequality for \f$L \setminus \{k\}\f$
1972 * and similarly for \f$k = \mbox{argmax}\{x^*_j \;:\; j \in L\}\f$.
1973 */
1974static
1976 SCIP* scip, /**< SCIP data structure */
1977 SCIP_CONS* cons, /**< constraint to check */
1978 SCIP_SOL* sol, /**< primal CIP solution, NULL for current LP solution */
1979 SCIP_Bool separateparity, /**< should parity inequalities be separated? */
1980 SCIP_Bool* separated, /**< pointer to store whether a cut was found */
1981 SCIP_Bool* cutoff /**< whether a cutoff has been detected */
1982 )
1983{
1984 SCIP_CONSDATA* consdata;
1985 SCIP_Real feasibility;
1986 int r;
1987
1988 assert( separated != NULL );
1989 assert( cutoff != NULL );
1990 *cutoff = FALSE;
1991
1992 consdata = SCIPconsGetData(cons);
1993 assert(consdata != NULL);
1994
1995 *separated = FALSE;
1996
1997 /* create row for the linear relaxation */
1998 if( consdata->rows[0] == NULL )
1999 {
2001 }
2002 assert(consdata->rows[0] != NULL);
2003
2004 /* test rows for feasibility and add it, if it is infeasible */
2005 for( r = 0; r < NROWS; ++r )
2006 {
2007 if( consdata->rows[r] != NULL && !SCIProwIsInLP(consdata->rows[r]) )
2008 {
2009 feasibility = SCIPgetRowSolFeasibility(scip, consdata->rows[r], sol);
2010 if( SCIPisFeasNegative(scip, feasibility) )
2011 {
2012 SCIP_CALL( SCIPaddRow(scip, consdata->rows[r], FALSE, cutoff) );
2013 if ( *cutoff )
2014 return SCIP_OKAY;
2015 *separated = TRUE;
2016 }
2017 }
2018 }
2019
2020 /* separate parity inequalities if required */
2021 if ( separateparity && consdata->nvars > 3 )
2022 {
2023 char name[SCIP_MAXSTRLEN];
2024 SCIP_Real maxval = -1.0;
2025 SCIP_Real minval = 2.0;
2026 SCIP_Real sum = 0.0;
2027 int maxidx = -1;
2028 int minidx = -1;
2029 int ngen = 0;
2030 int cnt = 0;
2031 int j;
2032
2033 SCIPdebugMsg(scip, "separating parity inequalities ...\n");
2034
2035 /* compute value */
2036 for (j = 0; j < consdata->nvars; ++j)
2037 {
2038 SCIP_Real val;
2039
2040 val = SCIPgetSolVal(scip, sol, consdata->vars[j]);
2041 if( val > 0.5 )
2042 {
2043 if ( val < minval )
2044 {
2045 minval = val;
2046 minidx = j;
2047 }
2048 ++cnt;
2049 sum += (1.0 - val);
2050 }
2051 else
2052 {
2053 if ( val > maxval )
2054 {
2055 maxval = val;
2056 maxidx = j;
2057 }
2058 sum += val;
2059 }
2060 }
2061
2062 /* if size of set does not have the same parity as rhs (e.g., size is odd if rhs is 0) */
2063 if ( (cnt - (int) consdata->rhs) % 2 == 1 )
2064 {
2065 if ( SCIPisEfficacious(scip, 1.0 - sum) )
2066 {
2067 SCIP_ROW* row;
2068
2069 SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f)\n", 1.0 - sum);
2070
2071 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2072 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real) (cnt - 1), FALSE, FALSE, TRUE) );
2074
2075 /* fill in row */
2076 for (j = 0; j < consdata->nvars; ++j)
2077 {
2078 if( SCIPgetSolVal(scip, sol, consdata->vars[j]) > 0.5 )
2079 {
2080 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2081 }
2082 else
2083 {
2084 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2085 }
2086 }
2089 SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
2090 assert( SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real) (cnt-1)) );
2091 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2092 ++ngen;
2093 }
2094 }
2095 else
2096 {
2097 /* If the parity is equal: check removing the element with smallest value from the set and adding the
2098 * element with largest value to the set. If we remove the element with smallest value, we have to subtract (1
2099 * - minval) and add minval to correct the sum. */
2100 if ( SCIPisEfficacious(scip, 1.0 - (sum - 1.0 + 2.0 * minval)) )
2101 {
2102 SCIP_ROW* row;
2103
2104 SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f, minval: %f)\n", 1.0 - (sum - 1.0 + 2.0 * minval), minval);
2105
2106 /* the rhs of the inequality is the corrected set size minus 1 */
2107 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2108 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real) (cnt - 2), FALSE, FALSE, TRUE) );
2110
2111 /* fill in row */
2112 for (j = 0; j < consdata->nvars; ++j)
2113 {
2114 if( SCIPgetSolVal(scip, sol, consdata->vars[j]) > 0.5 )
2115 {
2116 /* if the index corresponds to the smallest element, we reverse the sign */
2117 if ( j == minidx )
2118 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2119 else
2120 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2121 }
2122 else
2123 {
2124 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2125 }
2126 }
2129 SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
2130 assert( SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real) (cnt-2)) );
2131 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2132 ++ngen;
2133 }
2134
2135 /* If we add the element with largest value, we have to add (1 - maxval) and subtract maxval to get the correct sum. */
2136 if ( SCIPisEfficacious(scip, 1.0 - (sum + 1.0 - 2.0 * maxval)) )
2137 {
2138 SCIP_ROW* row;
2139
2140 SCIPdebugMsg(scip, "found violated parity cut (efficiacy: %f, maxval: %f)\n", 1.0 - (sum + 1.0 - 2.0 * maxval), maxval);
2141
2142 /* the rhs of the inequality is the size of the corrected set */
2143 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "parity#%s", SCIPconsGetName(cons));
2144 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), (SCIP_Real) cnt, FALSE, FALSE, TRUE) );
2146
2147 /* fill in row */
2148 for (j = 0; j < consdata->nvars; ++j)
2149 {
2150 if( SCIPgetSolVal(scip, sol, consdata->vars[j]) > 0.5 )
2151 {
2152 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2153 }
2154 else
2155 {
2156 /* if the index corresponds to the largest element, we reverse the sign */
2157 if ( j == maxidx )
2158 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], 1.0) );
2159 else
2160 SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->vars[j], -1.0) );
2161 }
2162 }
2165 SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
2166 assert( SCIPisGT(scip, SCIPgetRowLPActivity(scip, row), (SCIP_Real)cnt) );
2167 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2168 ++ngen;
2169 }
2170 }
2171
2172 SCIPdebugMsg(scip, "separated parity inequalites: %d\n", ngen);
2173 if ( ngen > 0 )
2174 *separated = TRUE;
2175 }
2176
2177 return SCIP_OKAY;
2178}
2179
2180/** Transform linear system \f$A x = b\f$ into row echelon form via the Gauss algorithm with row pivoting over GF2
2181 * @returns the rank of @p A
2182 *
2183 * 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
2184 * 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
2185 * s[i] contains the column index of the first nonzero in row @p i.
2186 */
2187static
2189 SCIP* scip, /**< SCIP data structure */
2190 int m, /**< number of rows */
2191 int n, /**< number of columns */
2192 int* p, /**< row permutation */
2193 int* s, /**< steps indicators of the row echelon form */
2194 Type** A, /**< matrix */
2195 Type* b /**< rhs */
2196 )
2197{
2198 int pi;
2199 int i;
2200 int j;
2201 int k;
2202
2203 assert( A != NULL );
2204 assert( b != NULL );
2205 assert( p != NULL );
2206 assert( s != NULL );
2207
2208 /* init permutation and step indicators */
2209 for (i = 0; i < m; ++i)
2210 {
2211 p[i] = i;
2212 s[i] = i;
2213 }
2214
2215 /* loop through possible steps in echelon form (stop at min {n, m}) */
2216 for (i = 0; i < m && i < n; ++i)
2217 {
2218 assert( s[i] == i );
2219
2220 /* init starting column */
2221 if ( i == 0 )
2222 j = 0;
2223 else
2224 j = s[i-1] + 1;
2225
2226 /* find pivot row (i.e., first nonzero entry), if all entries in current row are 0 we search the next column */
2227 do
2228 {
2229 /* search in current column j */
2230 k = i;
2231 while ( k < m && A[p[k]][j] == 0 )
2232 ++k;
2233
2234 /* found pivot */
2235 if ( k < m )
2236 break;
2237
2238 /* otherwise search next column */
2239 ++j;
2240 }
2241 while ( j < n );
2242
2243 /* if not pivot entry was found (checked all columns), the rank of A is equal to the current index i; in this case
2244 * all entries in and below row i are 0 */
2245 if ( j >= n )
2246 return i;
2247
2248 /* at this place: we have found a pivot entry (p[k], j) */
2249 assert( k < m );
2250
2251 /* store step index */
2252 s[i] = j;
2253 assert( A[p[k]][j] != 0 );
2254
2255 /* swap row indices */
2256 if ( k != i )
2257 {
2258 int h = p[i];
2259 p[i] = p[k];
2260 p[k] = h;
2261 }
2262 pi = p[i];
2263 assert( A[pi][s[i]] != 0 );
2264
2265 /* do elimination */
2266 for (k = i+1; k < m; ++k)
2267 {
2268 int pk = p[k];
2269 /* if entry in leading column is nonzero (otherwise we already have a 0) */
2270 if ( A[pk][s[i]] != 0 )
2271 {
2272 for (j = s[i]; j < n; ++j)
2273 A[pk][j] = A[pk][j] ^ A[pi][j]; /*lint !e732*/
2274 b[pk] = b[pk] ^ b[pi]; /*lint !e732*/
2275 }
2276 }
2277
2278 /* check stopped (only every 100 rows in order to save time */
2279 if ( i % 100 == 99 )
2280 {
2281 if ( SCIPisStopped(scip) )
2282 return -1;
2283 }
2284 }
2285
2286 /* 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
2287 * columns min {n,m}. */
2288 if ( n <= m )
2289 return n;
2290 return m;
2291}
2292
2293/** Construct solution from matrix in row echelon form over GF2
2294 *
2295 * Compute solution of \f$A x = b\f$, which is already in row echelon form (@see computeRowEchelonGF2()) */
2296static
2298 int m, /**< number of rows */
2299 int n, /**< number of columns */
2300 int r, /**< rank of matrix */
2301 int* p, /**< row permutation */
2302 int* s, /**< steps indicators of the row echelon form */
2303 Type** A, /**< matrix */
2304 Type* b, /**< rhs */
2305 Type* x /**< solution vector on exit */
2306 )
2307{
2308 int i;
2309 int k;
2310
2311 assert( A != NULL );
2312 assert( b != NULL );
2313 assert( s != NULL );
2314 assert( p != NULL );
2315 assert( x != NULL );
2316 assert( r <= m && r <= n );
2317
2318 /* init solution vector to 0 */
2319 for (k = 0; k < n; ++k)
2320 x[k] = 0;
2321
2322 /* loop backwards through solution vector */
2323 for (i = r-1; i >= 0; --i)
2324 {
2325 Type val;
2326
2327 assert( i <= s[i] && s[i] <= n );
2328
2329 /* init val with rhs and then add the contributions of the components of x already computed */
2330 val = b[p[i]];
2331 for (k = i+1; k < r; ++k)
2332 {
2333 assert( i <= s[k] && s[k] <= n );
2334 if ( A[p[i]][s[k]] != 0 )
2335 val = val ^ x[s[k]]; /*lint !e732*/
2336 }
2337
2338 /* store solution */
2339 x[s[i]] = val;
2340 }
2341}
2342
2343/** solve equation system over GF 2 by Gauss algorithm and create solution out of it or return cutoff
2344 *
2345 * Collect all information in xor constraints into a linear system over GF2. Then solve the system by computing a row
2346 * echelon form. If the system is infeasible, the current node is infeasible. Otherwise, we can compute a solution for
2347 * the xor constraints given. We check whether this gives a solution for the whole problem.
2348 *
2349 * We sort the columns with respect to the product of the objective coefficients and 1 minus the current LP solution
2350 * value. The idea is that columns that are likely to provide the steps in the row echelon form should appear towards
2351 * the front of the matrix. The smaller the product, the more it makes sense to set the variable to 1 (because the
2352 * solution value is already close to 1 and the objective function is small).
2353 *
2354 * Note that this function is called from propagation where usually no solution is available. However, the solution is
2355 * only used for sorting the columns. Thus, the procedure stays correct even with nonsense solutions.
2356 */
2357static
2359 SCIP* scip, /**< SCIP data structure */
2360 SCIP_CONS** conss, /**< xor constraints */
2361 int nconss, /**< number of xor constraints */
2362 SCIP_SOL* currentsol, /**< current solution (maybe NULL) */
2363 SCIP_RESULT* result /**< result of propagation (possibly cutoff, no change if primal solution has been tried) */
2364 )
2365{
2366 SCIP_CONSDATA* consdata;
2367 SCIP_HASHMAP* varhash;
2368 SCIP_Bool* xoractive;
2369 SCIP_Real* xorvals;
2370 SCIP_VAR** xorvars;
2371 SCIP_Bool noaggr = TRUE;
2372 Type** A;
2373 Type* b;
2374 int* s;
2375 int* p;
2376 int* xoridx;
2377 int* xorbackidx;
2378 int nconssactive = 0;
2379 int nconssmat = 0;
2380 int nvarsmat = 0;
2381 int nvars;
2382 int rank;
2383 int i;
2384 int j;
2385
2386 assert( scip != NULL );
2387 assert( conss != NULL );
2388 assert( result != NULL );
2389
2390 if ( *result == SCIP_CUTOFF )
2391 return SCIP_OKAY;
2392
2393 SCIPdebugMsg(scip, "Checking feasibility via the linear equation system over GF2 using Gauss.\n");
2394
2395 nvars = SCIPgetNVars(scip);
2396
2397 /* set up hash map from variable to column index */
2398 SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), nvars) );
2399 SCIP_CALL( SCIPallocBufferArray(scip, &xoractive, nconss) );
2400 SCIP_CALL( SCIPallocBufferArray(scip, &xorvars, nvars) );
2401 SCIP_CALL( SCIPallocBufferArray(scip, &xoridx, nvars) );
2402 SCIP_CALL( SCIPallocBufferArray(scip, &xorvals, nvars) );
2403
2404 /* collect variables */
2405 for (i = 0; i < nconss; ++i)
2406 {
2407 int cnt = 0;
2408
2409 xoractive[i] = FALSE;
2410
2411 assert( conss[i] != NULL );
2412 consdata = SCIPconsGetData(conss[i]);
2413 assert( consdata != NULL );
2414
2415 /* count nonfixed variables in constraint */
2416 for (j = 0; j < consdata->nvars; ++j)
2417 {
2418 SCIP_VAR* var;
2419
2420 var = consdata->vars[j];
2421 assert( var != NULL );
2422 assert( SCIPvarIsBinary(var) );
2423
2424 /* replace negated variables */
2425 if ( SCIPvarIsNegated(var) )
2426 var = SCIPvarGetNegatedVar(var);
2427 assert( var != NULL );
2428
2429 /* get the active variable */
2430 while ( var != NULL && SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED )
2431 var = SCIPisEQ(scip, SCIPvarGetAggrScalar(var), 0.0) ? NULL : SCIPvarGetAggrVar(var);
2432 /* consider nonfixed variables */
2433 if ( var != NULL && SCIPcomputeVarLbLocal(scip, var) < 0.5 && SCIPcomputeVarUbLocal(scip, var) > 0.5 )
2434 {
2435 /* consider active variables and collect only new ones */
2436 if ( SCIPvarIsActive(var) && ! SCIPhashmapExists(varhash, var) )
2437 {
2438 /* add variable in map */
2439 SCIP_CALL( SCIPhashmapInsertInt(varhash, var, nvarsmat) );
2440 assert( nvarsmat == SCIPhashmapGetImageInt(varhash, var) );
2441 xorvals[nvarsmat] = SCIPvarGetObj(var) * (1.0 - SCIPgetSolVal(scip, currentsol, var));
2442 xorvars[nvarsmat++] = var;
2443 }
2444 ++cnt;
2445 }
2446 }
2447
2448 if ( cnt > 0 )
2449 {
2450 xoractive[i] = TRUE;
2451 ++nconssactive;
2452 }
2453#ifdef SCIP_DISABLED_CODE
2454 /* The following can save time, if there are constraints with all variables fixed that are infeasible; this
2455 * should, however, be detected somewhere else, e.g., in propagateCons(). */
2456 else
2457 {
2458 /* all variables are fixed - check whether constraint is feasible (could be that the constraint is not propagated) */
2459 assert( cnt == 0 );
2460 for (j = 0; j < consdata->nvars; ++j)
2461 {
2462 /* count variables fixed to 1 */
2463 if ( SCIPcomputeVarLbLocal(scip, consdata->vars[j]) > 0.5 )
2464 ++cnt;
2465 else
2466 assert( SCIPcomputeVarUbLocal(scip, consdata->vars[j]) < 0.5 );
2467 }
2468 if ( ( cnt - consdata->rhs ) % 2 != 0 )
2469 {
2470 SCIPdebugMsg(scip, "constraint <%s> with all variables fixed is violated.\n", SCIPconsGetName(conss[i]));
2471 *result = SCIP_CUTOFF;
2472 break;
2473 }
2474 }
2475#endif
2476 }
2477 assert( nvarsmat <= nvars );
2478 assert( nconssactive <= nconss );
2479
2480 if ( nconssactive > MAXXORCONSSSYSTEM || nvarsmat > MAXXORVARSSYSTEM || *result == SCIP_CUTOFF )
2481 {
2482 SCIPdebugMsg(scip, "Skip checking the xor system over GF2 (%d conss, %d vars).\n", nconssactive, nvarsmat);
2483 SCIPfreeBufferArray(scip, &xorvals);
2484 SCIPfreeBufferArray(scip, &xoridx);
2485 SCIPfreeBufferArray(scip, &xorvars);
2486 SCIPfreeBufferArray(scip, &xoractive);
2487 SCIPhashmapFree(&varhash);
2488 return SCIP_OKAY;
2489 }
2490
2491 /* init index */
2492 for (j = 0; j < nvarsmat; ++j)
2493 xoridx[j] = j;
2494
2495 /* Sort variables non-decreasingly with respect to product of objective and 1 minus the current solution value: the
2496 * smaller the value the better it would be to set the variable to 1. This is more likely if the variable appears
2497 * towards the front of the matrix, because only the entries on the steps in the row echelon form will have the
2498 * chance to be nonzero.
2499 */
2500 SCIPsortRealIntPtr(xorvals, xoridx, (void**) xorvars, nvarsmat);
2501 SCIPfreeBufferArray(scip, &xorvals);
2502
2503 /* build back index */
2504 SCIP_CALL( SCIPallocBufferArray(scip, &xorbackidx, nvarsmat) );
2505 for (j = 0; j < nvarsmat; ++j)
2506 {
2507 assert( 0 <= xoridx[j] && xoridx[j] < nvarsmat );
2508 xorbackidx[xoridx[j]] = j;
2509 }
2510
2511 /* init matrix and rhs */
2512 SCIP_CALL( SCIPallocBufferArray(scip, &b, nconssactive) );
2513 SCIP_CALL( SCIPallocBufferArray(scip, &A, nconssactive) );
2514 for (i = 0; i < nconss; ++i)
2515 {
2516 if ( ! xoractive[i] )
2517 continue;
2518
2519 assert( conss[i] != NULL );
2520 consdata = SCIPconsGetData(conss[i]);
2521 assert( consdata != NULL );
2522 assert( consdata->nvars > 0 );
2523
2524 SCIP_CALL( SCIPallocBufferArray(scip, &(A[nconssmat]), nvarsmat) ); /*lint !e866*/
2525 BMSclearMemoryArray(A[nconssmat], nvarsmat); /*lint !e866*/
2526
2527 /* correct rhs w.r.t. to fixed variables and count nonfixed variables in constraint */
2528 b[nconssmat] = (Type) consdata->rhs;
2529 for (j = 0; j < consdata->nvars; ++j)
2530 {
2531 SCIP_VAR* var;
2532 int idx;
2533
2534 var = consdata->vars[j];
2535 assert( var != NULL );
2536
2537 /* replace negated variables */
2538 if ( SCIPvarIsNegated(var) )
2539 {
2540 var = SCIPvarGetNegatedVar(var);
2541 assert( var != NULL );
2542 b[nconssmat] = ! b[nconssmat];
2543 }
2544
2545 /* replace aggregated variables */
2547 {
2548 SCIP_Real scalar;
2549 SCIP_Real constant;
2550
2551 scalar = SCIPvarGetAggrScalar(var);
2552 constant = SCIPvarGetAggrConstant(var);
2553
2554 /* the variable resolves to a constant, we just update the rhs */
2555 if( SCIPisEQ(scip, scalar, 0.0) )
2556 {
2557 assert(SCIPisEQ(scip, constant, 0.0) || SCIPisEQ(scip, constant, 1.0));
2558 if( SCIPisEQ(scip, constant, 1.0) )
2559 b[nconssmat] = ! b[nconssmat];
2560 var = NULL;
2561 break;
2562 }
2563 /* replace aggregated variable by active variable and update rhs, if needed */
2564 else
2565 {
2566 assert(SCIPisEQ(scip, scalar, 1.0) || SCIPisEQ(scip, scalar, -1.0));
2567 if( SCIPisEQ(scip, constant, 1.0) )
2568 b[nconssmat] = ! b[nconssmat];
2569
2570 var = SCIPvarGetAggrVar(var);
2571 assert(var != NULL);
2572 }
2573 }
2574 /* variable resolved to a constant */
2575 if( var == NULL )
2576 continue;
2577
2578 /* If the constraint contains multiaggregated variables, the solution might not be valid, since the
2579 * implications are not represented in the matrix.
2580 */
2582 noaggr = FALSE;
2583
2584 if ( SCIPcomputeVarLbLocal(scip, var) > 0.5 )
2585 {
2586 /* variable is fixed to 1, invert rhs */
2587 b[nconssmat] = ! b[nconssmat];
2588 assert( ! SCIPhashmapExists(varhash, var) );
2589 }
2590 else
2591 {
2594 if ( SCIPvarIsActive(var) && SCIPcomputeVarUbLocal(scip, var) > 0.5 )
2595 {
2596 assert( SCIPhashmapExists(varhash, var) );
2597 idx = SCIPhashmapGetImageInt(varhash, var);
2598 assert( idx < nvarsmat );
2599 assert( 0 <= xorbackidx[idx] && xorbackidx[idx] < nvarsmat );
2600 A[nconssmat][xorbackidx[idx]] = 1;
2601 }
2602 }
2603 }
2604 ++nconssmat;
2605 }
2606 SCIPdebugMsg(scip, "Found %d non-fixed variables in %d nonempty xor constraints.\n", nvarsmat, nconssmat);
2607 assert( nconssmat == nconssactive );
2608
2609 /* perform Gauss algorithm */
2610 SCIP_CALL( SCIPallocBufferArray(scip, &p, nconssmat) );
2611 SCIP_CALL( SCIPallocBufferArray(scip, &s, nconssmat) );
2612
2613#ifdef SCIP_OUTPUT
2614 SCIPinfoMessage(scip, NULL, "Matrix before Gauss (size: %d x %d):\n", nconssmat, nvarsmat);
2615 for (i = 0; i < nconssmat; ++i)
2616 {
2617 for (j = 0; j < nvarsmat; ++j)
2618 SCIPinfoMessage(scip, NULL, "%d ", A[i][j]);
2619 SCIPinfoMessage(scip, NULL, " = %d\n", b[i]);
2620 }
2621 SCIPinfoMessage(scip, NULL, "\n");
2622#endif
2623
2624 rank = -1;
2625 if ( ! SCIPisStopped(scip) )
2626 {
2627 rank = computeRowEchelonGF2(scip, nconssmat, nvarsmat, p, s, A, b);
2628 assert( rank <= nconssmat && rank <= nvarsmat );
2629 }
2630
2631 /* rank is < 0 if the solution process has been stopped */
2632 if ( rank >= 0 )
2633 {
2634#ifdef SCIP_OUTPUT
2635 SCIPinfoMessage(scip, NULL, "Matrix after Gauss (rank: %d):\n", rank);
2636 for (i = 0; i < nconssmat; ++i)
2637 {
2638 for (j = 0; j < nvarsmat; ++j)
2639 SCIPinfoMessage(scip, NULL, "%d ", A[p[i]][j]);
2640 SCIPinfoMessage(scip, NULL, " = %d\n", b[p[i]]);
2641 }
2642 SCIPinfoMessage(scip, NULL, "\n");
2643#endif
2644
2645 /* check whether system is feasible */
2646 for (i = rank; i < nconssmat; ++i)
2647 {
2648 if ( b[p[i]] != 0 )
2649 break;
2650 }
2651
2652 /* did not find nonzero entry in b -> equation system is feasible */
2653 if ( i >= nconssmat )
2654 {
2655 SCIPdebugMsg(scip, "System feasible with rank %d (nconss=%d)\n", rank, nconssmat);
2656
2657 /* matrix has full rank, solution is unique */
2658 if( rank == nvarsmat && noaggr )
2659 {
2660 SCIP_Bool tightened;
2661 SCIP_Bool infeasible;
2662 Type* x;
2663
2664 SCIPdebugMsg(scip, "Found unique solution.\n");
2665
2666 /* construct solution */
2667 SCIP_CALL( SCIPallocBufferArray(scip, &x, nvarsmat) );
2668 solveRowEchelonGF2(nconssmat, nvarsmat, rank, p, s, A, b, x);
2669
2670#ifdef SCIP_OUTPUT
2671 SCIPinfoMessage(scip, NULL, "Solution:\n");
2672 for (j = 0; j < nvarsmat; ++j)
2673 SCIPinfoMessage(scip, NULL, "%d ", x[j]);
2674 SCIPinfoMessage(scip, NULL, "\n");
2675#endif
2676
2677 /* fix variables according to computed unique solution */
2678 for( j = 0; j < nvarsmat; ++j )
2679 {
2680 assert( SCIPhashmapGetImageInt(varhash, xorvars[j]) < nvars );
2681 assert( xorbackidx[SCIPhashmapGetImageInt(varhash, xorvars[j])] == j );
2682 assert( SCIPcomputeVarLbLocal(scip, xorvars[j]) < 0.5 );
2683 if( x[j] == 0 )
2684 {
2685 SCIP_CALL( SCIPtightenVarUb(scip, xorvars[j], 0.0, FALSE, &infeasible, &tightened) );
2686 assert(tightened);
2687 assert(!infeasible);
2688 }
2689 else
2690 {
2691 assert(x[j] == 1);
2692 SCIP_CALL( SCIPtightenVarLb(scip, xorvars[j], 1.0, FALSE, &infeasible, &tightened) );
2693 assert(tightened);
2694 assert(!infeasible);
2695 }
2696 }
2698 }
2699 /* matrix does not have full rank, we add the solution, but cannot derive fixings */
2700 else
2701 {
2702 SCIP_HEUR* heurtrysol;
2703
2704 SCIPdebugMsg(scip, "Found solution.\n");
2705
2706 /* try solution */
2707 heurtrysol = SCIPfindHeur(scip, "trysol");
2708
2709 if ( heurtrysol != NULL )
2710 {
2711 SCIP_Bool success;
2712 SCIP_VAR** vars;
2713 SCIP_SOL* sol;
2714 Type* x;
2715
2716 /* construct solution */
2717 SCIP_CALL( SCIPallocBufferArray(scip, &x, nvarsmat) );
2718 solveRowEchelonGF2(nconssmat, nvarsmat, rank, p, s, A, b, x);
2719
2720#ifdef SCIP_OUTPUT
2721 SCIPinfoMessage(scip, NULL, "Solution:\n");
2722 for (j = 0; j < nvarsmat; ++j)
2723 SCIPinfoMessage(scip, NULL, "%d ", x[j]);
2724 SCIPinfoMessage(scip, NULL, "\n");
2725#endif
2726
2727 /* create solution */
2728 SCIP_CALL( SCIPcreateSol(scip, &sol, heurtrysol) );
2729
2730 /* transfer solution */
2731 for (j = 0; j < nvarsmat; ++j)
2732 {
2733 if ( x[j] != 0 )
2734 {
2735 assert( SCIPhashmapGetImageInt(varhash, xorvars[j]) < nvars );
2736 assert( xorbackidx[SCIPhashmapGetImageInt(varhash, xorvars[j])] == j );
2737 assert( SCIPcomputeVarLbLocal(scip, xorvars[j]) < 0.5 );
2738 SCIP_CALL( SCIPsetSolVal(scip, sol, xorvars[j], 1.0) );
2739 }
2740 }
2742
2743 /* add *all* variables fixed to 1 */
2744 vars = SCIPgetVars(scip);
2745 for (j = 0; j < nvars; ++j)
2746 {
2747 if ( SCIPcomputeVarLbLocal(scip, vars[j]) > 0.5 )
2748 {
2749 SCIP_CALL( SCIPsetSolVal(scip, sol, vars[j], 1.0) );
2750 SCIPdebugMsg(scip, "Added fixed variable <%s>.\n", SCIPvarGetName(vars[j]));
2751 }
2752 }
2753
2754 /* correct integral variables if necessary */
2755 for (i = 0; i < nconss; ++i)
2756 {
2757 consdata = SCIPconsGetData(conss[i]);
2758 assert(consdata != NULL);
2759
2760 /* only try for active constraints and integral variable; hope for the best if they are not active */
2761 if ( xoractive[i] && consdata->intvar != NULL && SCIPvarIsActive(consdata->intvar) )
2762 {
2763 SCIP_Real val;
2764 int nones = 0;
2765
2766 for (j = 0; j < consdata->nvars; ++j)
2767 {
2768 if ( SCIPgetSolVal(scip, sol, consdata->vars[j]) > 0.5 )
2769 ++nones;
2770 }
2771 /* if there are aggregated variables, the solution might not be feasible */
2772 assert( ! noaggr || nones % 2 == (int) consdata->rhs );
2773 if ( (unsigned int) nones != consdata->rhs )
2774 {
2775 val = (SCIP_Real) (nones - (int) consdata->rhs)/2;
2776 if ( SCIPisGE(scip, val, SCIPvarGetLbGlobal(consdata->intvar)) && SCIPisLE(scip, val, SCIPvarGetUbGlobal(consdata->intvar)) )
2777 {
2778 SCIP_CALL( SCIPsetSolVal(scip, sol, consdata->intvar, val) );
2779 }
2780 }
2781 }
2782 }
2784
2785 /* check feasibility of new solution and pass it to trysol heuristic */
2786 SCIP_CALL( SCIPcheckSol(scip, sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2787 if ( success )
2788 {
2789 SCIP_CALL( SCIPheurPassSolAddSol(scip, heurtrysol, sol) );
2790 SCIPdebugMsg(scip, "Creating solution was successful.\n");
2791 }
2792#ifdef SCIP_DEBUG
2793 else
2794 {
2795 /* the solution might not be feasible, because of additional constraints */
2796 SCIPdebugMsg(scip, "Creating solution was not successful.\n");
2797 }
2798#endif
2799 SCIP_CALL( SCIPfreeSol(scip, &sol) );
2800 }
2801 }
2802 }
2803 else
2804 {
2805 *result = SCIP_CUTOFF;
2806 SCIPdebugMsg(scip, "System not feasible.\n");
2807 }
2808 }
2809
2810 /* free storage */
2813 j = nconssmat - 1;
2814 for (i = nconss - 1; i >= 0 ; --i)
2815 {
2816 consdata = SCIPconsGetData(conss[i]);
2817 assert(consdata != NULL);
2818
2819 if ( consdata->nvars == 0 )
2820 continue;
2821
2822 if( !xoractive[i] )
2823 continue;
2824
2825 SCIPfreeBufferArray(scip, &(A[j]));
2826 --j;
2827 }
2830 SCIPfreeBufferArray(scip, &xorbackidx);
2831 SCIPfreeBufferArray(scip, &xoridx);
2832 SCIPfreeBufferArray(scip, &xorvars);
2833 SCIPfreeBufferArray(scip, &xoractive);
2834 SCIPhashmapFree(&varhash);
2835
2836 return SCIP_OKAY;
2837}
2838
2839/** for each variable in the xor constraint, add it to conflict set; for integral variable add corresponding bound */
2840static
2842 SCIP* scip, /**< SCIP data structure */
2843 SCIP_CONS* cons, /**< constraint that inferred the bound change */
2844 SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2845 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
2846 PROPRULE proprule /**< propagation rule */
2847 )
2848{
2849 SCIP_CONSDATA* consdata;
2850 SCIP_VAR** vars;
2851 int nvars;
2852 int i;
2853
2854 assert( cons != NULL );
2855
2856 consdata = SCIPconsGetData(cons);
2857 assert(consdata != NULL);
2858 vars = consdata->vars;
2859 nvars = consdata->nvars;
2860
2861 switch( proprule )
2862 {
2863 case PROPRULE_0:
2864 assert( infervar == NULL || infervar == consdata->intvar );
2865
2866 /* the integral variable was fixed, because all variables were fixed */
2867 for (i = 0; i < nvars; ++i)
2868 {
2869 assert( SCIPisEQ(scip, SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE), SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE)) );
2871 }
2872 break;
2873
2874 case PROPRULE_1:
2875 /* the variable was inferred, because all other variables were fixed */
2876 for (i = 0; i < nvars; ++i)
2877 {
2878 /* add variables that were fixed to 1 before */
2879 if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2880 {
2881 assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2883 }
2884 /* add variables that were fixed to 0 */
2885 else if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2886 {
2887 assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2889 }
2890 else
2891 {
2892 /* check changed variable (changed variable is 0 or 1 afterwards) */
2893 assert( vars[i] == infervar );
2894 }
2895 }
2896 break;
2897
2898 case PROPRULE_INTLB:
2899 assert( consdata->intvar != NULL );
2900
2901 if( infervar != consdata->intvar )
2902 {
2903 /* the variable was fixed, because of the lower bound of the integral variable */
2904 SCIP_CALL( SCIPaddConflictLb(scip, consdata->intvar, NULL) );
2905 }
2906 /* to many and the other fixed variables */
2907 for (i = 0; i < nvars; ++i)
2908 {
2909 /* add variables that were fixed to 0 */
2910 if ( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, FALSE) < 0.5 )
2911 {
2912 assert( SCIPgetVarUbAtIndex(scip, vars[i], bdchgidx, TRUE) < 0.5 );
2914 }
2915 }
2916 break;
2917
2918 case PROPRULE_INTUB:
2919 assert( consdata->intvar != NULL );
2920
2921 if( infervar != consdata->intvar )
2922 {
2923 /* the variable was fixed, because of upper bound of the integral variable and the other fixed variables */
2924 SCIP_CALL( SCIPaddConflictUb(scip, consdata->intvar, NULL) );
2925 }
2926 for (i = 0; i < nvars; ++i)
2927 {
2928 /* add variables that were fixed to 1 */
2929 if ( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, FALSE) > 0.5 )
2930 {
2931 assert( SCIPgetVarLbAtIndex(scip, vars[i], bdchgidx, TRUE) > 0.5 );
2933 }
2934 }
2935 break;
2936
2937 case PROPRULE_INVALID:
2938 default:
2939 SCIPerrorMessage("invalid inference information %d in xor constraint <%s>\n", proprule, SCIPconsGetName(cons));
2940 SCIPABORT();
2941 return SCIP_INVALIDDATA; /*lint !e527*/
2942 }
2943
2944 return SCIP_OKAY;
2945}
2946
2947/** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
2948static
2950 SCIP* scip, /**< SCIP data structure */
2951 SCIP_CONS* cons, /**< xor constraint that detected the conflict */
2952 SCIP_VAR* infervar, /**< variable that was deduced, or NULL (not equal to integral variable) */
2953 PROPRULE proprule /**< propagation rule */
2954 )
2955{
2956 /* conflict analysis can only be applied in solving stage and if it is applicable */
2958 return SCIP_OKAY;
2959
2960 /* initialize conflict analysis, and add all variables of infeasible constraint to conflict candidate queue */
2962
2963 /* add bound changes */
2964 SCIP_CALL( addConflictBounds(scip, cons, infervar, NULL, proprule) );
2965
2966 /* analyze the conflict */
2968
2969 return SCIP_OKAY;
2970}
2971
2972/** propagates constraint with the following rules:
2973 * (0) all variables are fixed => can fix integral variable
2974 * (1) all except one variable fixed => fix remaining variable and integral variable
2975 * (2) depending on the amount of fixed binary variables we can tighten the integral variable
2976 * (3) depending on the lower bound of the integral variable one can fix variables to 1
2977 * (4) depending on the upper bound of the integral variable one can fix variables to 0
2978 */
2979static
2981 SCIP* scip, /**< SCIP data structure */
2982 SCIP_CONS* cons, /**< xor constraint to be processed */
2983 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
2984 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
2985 int* nfixedvars, /**< pointer to add up the number of fixed variables */
2986 int* nchgbds /**< pointer to add up the number of found domain reductions */
2987 )
2988{
2989 SCIP_CONSDATA* consdata;
2990 SCIP_VAR** vars;
2991 SCIP_Bool infeasible;
2992 SCIP_Bool tightened;
2993 SCIP_Bool odd;
2994 SCIP_Bool counted;
2995 int nvars;
2996 int nfixedones;
2997 int nfixedzeros;
2998 int watchedvar1;
2999 int watchedvar2;
3000 int i;
3001
3002 assert(scip != NULL);
3003 assert(cons != NULL);
3004 assert(eventhdlr != NULL);
3005 assert(cutoff != NULL);
3006 assert(nfixedvars != NULL);
3007 assert(nchgbds != NULL);
3008
3009 /* propagation can only be applied, if we know all operator variables */
3010 if( SCIPconsIsModifiable(cons) )
3011 return SCIP_OKAY;
3012
3013 consdata = SCIPconsGetData(cons);
3014 assert(consdata != NULL);
3015
3016 vars = consdata->vars;
3017 nvars = consdata->nvars;
3018
3019 /* don't process the constraint, if the watched variables weren't fixed to any value since last propagation call */
3020 if( consdata->propagated )
3021 return SCIP_OKAY;
3022
3023 /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
3025 {
3026 SCIP_CALL( SCIPincConsAge(scip, cons) );
3027 }
3028
3029 /* propagation cannot be applied, if we have at least two unfixed variables left;
3030 * that means, we only have to watch (i.e. capture events) of two variables, and switch to other variables
3031 * if these ones get fixed
3032 */
3033 watchedvar1 = consdata->watchedvar1;
3034 watchedvar2 = consdata->watchedvar2;
3035
3036 /* check, if watched variables are still unfixed */
3037 if( watchedvar1 != -1 )
3038 {
3039 if( SCIPvarGetLbLocal(vars[watchedvar1]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar1]) < 0.5 )
3040 watchedvar1 = -1;
3041 }
3042 if( watchedvar2 != -1 )
3043 {
3044 if( SCIPvarGetLbLocal(vars[watchedvar2]) > 0.5 || SCIPvarGetUbLocal(vars[watchedvar2]) < 0.5 )
3045 watchedvar2 = -1;
3046 }
3047
3048 /* if only one watched variable is still unfixed, make it the first one */
3049 if( watchedvar1 == -1 )
3050 {
3051 watchedvar1 = watchedvar2;
3052 watchedvar2 = -1;
3053 }
3054 assert(watchedvar1 != -1 || watchedvar2 == -1);
3055
3056 /* if the watched variables are invalid (fixed), find new ones if existing; count the parity */
3057 odd = consdata->rhs;
3058 nfixedones = 0;
3059 nfixedzeros = 0;
3060 counted = FALSE;
3061 if( watchedvar2 == -1 )
3062 {
3063 for( i = 0; i < nvars; ++i )
3064 {
3065 if( SCIPvarGetLbLocal(vars[i]) > 0.5 )
3066 {
3067 odd = !odd;
3068 ++nfixedones;
3069 }
3070 else if( SCIPvarGetUbLocal(vars[i]) < 0.5 )
3071 ++nfixedzeros;
3072 else
3073 {
3074 assert(SCIPvarGetUbLocal(vars[i]) > 0.5);
3075 assert(SCIPvarGetLbLocal(vars[i]) < 0.5);
3076
3077 if( watchedvar1 == -1 )
3078 {
3079 assert(watchedvar2 == -1);
3080 watchedvar1 = i;
3081 }
3082 else if( watchedvar2 == -1 && watchedvar1 != i )
3083 {
3084 watchedvar2 = i;
3085 }
3086 }
3087 }
3088 counted = TRUE;
3089 }
3090 assert(watchedvar1 != -1 || watchedvar2 == -1);
3091
3092 /* if all variables are fixed, we can decide the feasibility of the constraint */
3093 if( watchedvar1 == -1 )
3094 {
3095 assert(watchedvar2 == -1);
3096 assert(counted);
3097
3098 if( odd )
3099 {
3100 SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is infeasible\n", SCIPconsGetName(cons));
3101
3102 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
3105
3106 *cutoff = TRUE;
3107 }
3108 else
3109 {
3110 /* fix integral variable if present */
3111 if ( consdata->intvar != NULL )
3112 {
3113 int fixval;
3114
3115 assert( ! *cutoff );
3116 assert( (nfixedones - (int) consdata->rhs) % 2 == 0 );
3117
3118 fixval = (nfixedones - (int) consdata->rhs)/2; /*lint !e713*/
3119
3120 SCIPdebugMsg(scip, "fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3121
3122 /* check whether value to fix is outside bounds */
3123 if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3124 {
3125 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3126 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3127 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3128
3131
3132 *cutoff = TRUE;
3133 }
3134 else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3135 {
3136 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3137 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3138 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3139
3142
3143 *cutoff = TRUE;
3144 }
3145 else if( SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3146 {
3147 if ( ! SCIPisEQ(scip, SCIPvarGetLbLocal(consdata->intvar), (SCIP_Real) fixval) )
3148 {
3149 SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3150 assert( tightened );
3151 assert( ! infeasible );
3152 }
3153
3154 if ( ! SCIPisEQ(scip, SCIPvarGetUbLocal(consdata->intvar), (SCIP_Real) fixval) )
3155 {
3156 SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_0, FALSE, &infeasible, &tightened) );
3157 assert( tightened );
3158 assert( ! infeasible );
3159 }
3160
3161 ++(*nfixedvars);
3162 }
3163 }
3164 else
3165 {
3166 SCIPdebugMsg(scip, "constraint <%s>: all vars fixed, constraint is feasible\n", SCIPconsGetName(cons));
3167 }
3168 }
3170
3171 return SCIP_OKAY;
3172 }
3173
3174 /* if only one variable is not fixed, this variable can be deduced */
3175 if( watchedvar2 == -1 )
3176 {
3177 assert(watchedvar1 != -1);
3178 assert(counted);
3179
3180 SCIPdebugMsg(scip, "constraint <%s>: only one unfixed variable -> fix <%s> to %u\n",
3181 SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]), odd);
3182
3183 SCIP_CALL( SCIPinferBinvarCons(scip, vars[watchedvar1], odd, cons, (int)PROPRULE_1, &infeasible, &tightened) );
3184 assert(!infeasible);
3185 assert(tightened);
3186
3187 (*nfixedvars)++;
3188
3189 /* fix integral variable if present and not multi-aggregated */
3190 if ( consdata->intvar != NULL && SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3191 {
3192 int fixval;
3193
3194 /* if variable has been fixed to 1, adjust number of fixed variables */
3195 if ( odd )
3196 ++nfixedones;
3197
3198 assert( (nfixedones - (int) consdata->rhs) % 2 == 0 );
3199
3200 fixval = (nfixedones - (int) consdata->rhs)/2; /*lint !e713*/
3201 SCIPdebugMsg(scip, "should fix integral variable <%s> to %d\n", SCIPvarGetName(consdata->intvar), fixval);
3202
3203 /* check whether value to fix is outside bounds */
3204 if ( fixval + 0.5 < SCIPvarGetLbLocal(consdata->intvar) )
3205 {
3206 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3207 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3208 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3209
3212
3213 *cutoff = TRUE;
3214 }
3215 else if ( fixval - 0.5 > SCIPvarGetUbLocal(consdata->intvar) )
3216 {
3217 /* cannot fix auxiliary variable (maybe it has been branched on): we are infeasible */
3218 SCIPdebugMsg(scip, "node infeasible: activity is %d, bounds of integral variable are [%g,%g]\n",
3219 fixval, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar));
3220
3223
3224 *cutoff = TRUE;
3225 }
3226 else
3227 {
3228 if( SCIPvarGetLbLocal(consdata->intvar) + 0.5 < (SCIP_Real) fixval )
3229 {
3230 SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3231 assert( tightened );
3232 assert( ! infeasible );
3233 }
3234
3235 if( SCIPvarGetUbLocal(consdata->intvar) - 0.5 > (SCIP_Real) fixval )
3236 {
3237 SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, (SCIP_Real) fixval, cons, (int)PROPRULE_1, TRUE, &infeasible, &tightened) );
3238 assert( tightened );
3239 assert( ! infeasible );
3240 }
3241 assert(SCIPisFeasEQ(scip, SCIPvarGetLbLocal(consdata->intvar), SCIPvarGetUbLocal(consdata->intvar)));
3242
3243 ++(*nfixedvars);
3244 }
3245 }
3246
3249
3250 return SCIP_OKAY;
3251 }
3252
3253 /* propagate w.r.t. integral variable */
3254 if ( consdata->intvar != NULL && !consdata->deleteintvar )
3255 {
3256 SCIP_Real newlb;
3257 SCIP_Real newub;
3258 int nonesmin;
3259 int nonesmax;
3260
3261 if( !counted )
3262 {
3263 assert(nfixedzeros == 0);
3264 assert(nfixedones == 0);
3265
3266 for( i = 0; i < nvars; ++i )
3267 {
3268 if( SCIPvarGetLbLocal(vars[i]) > 0.5 )
3269 ++nfixedones;
3270 else if( SCIPvarGetUbLocal(vars[i]) < 0.5 )
3271 ++nfixedzeros;
3272 }
3273 }
3274 assert( nfixedones + nfixedzeros < nvars );
3275
3276 assert( SCIPisFeasIntegral(scip, SCIPvarGetLbLocal(consdata->intvar)) );
3277 assert( SCIPisFeasIntegral(scip, SCIPvarGetUbLocal(consdata->intvar)) );
3278
3279 nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3280 nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3281
3282 /* the number of possible variables that can get value 1 is less than the minimum bound */
3283 if ( nvars - nfixedzeros < nonesmin )
3284 {
3285 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);
3286
3289
3290 *cutoff = TRUE;
3291
3292 return SCIP_OKAY;
3293 }
3294
3295 /* the number of variables that are fixed to 1 is larger than the maximum bound */
3296 if ( nfixedones > nonesmax )
3297 {
3298 SCIPdebugMsg(scip, "constraint <%s>: at least %d variables are fixed to 1, but there should be at most %d.\n", SCIPconsGetName(cons), nfixedones, nonesmax);
3299
3302
3303 *cutoff = TRUE;
3304
3305 return SCIP_OKAY;
3306 }
3307
3308 if( SCIPvarGetStatus(consdata->intvar) != SCIP_VARSTATUS_MULTAGGR )
3309 {
3310 /* compute new bounds on the integral variable */
3311 newlb = (SCIP_Real)((nfixedones + 1 - (int) consdata->rhs) / 2); /*lint !e653*/
3312 newub = (SCIP_Real)((nvars - nfixedzeros - (int) consdata->rhs) / 2); /*lint !e653*/
3313
3314 /* new lower bound is better */
3315 if( newlb > SCIPvarGetLbLocal(consdata->intvar) + 0.5 )
3316 {
3317 SCIPdebugMsg(scip, "constraint <%s>: propagated lower bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newlb);
3318 SCIP_CALL( SCIPinferVarLbCons(scip, consdata->intvar, newlb, cons, (int)PROPRULE_INTUB, TRUE, &infeasible, &tightened) );
3319 assert(tightened);
3320 assert(!infeasible);
3321
3322 ++(*nchgbds);
3323
3324 nonesmin = 2 * (int)(SCIPvarGetLbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3325 }
3326
3327 /* new upper bound is better */
3328 if( newub < SCIPvarGetUbLocal(consdata->intvar) - 0.5 )
3329 {
3330 SCIPdebugMsg(scip, "constraint <%s>: propagated upper bound of integral variable <%s> to %g\n", SCIPconsGetName(cons), SCIPvarGetName(consdata->intvar), newub);
3331 SCIP_CALL( SCIPinferVarUbCons(scip, consdata->intvar, newub, cons, (int)PROPRULE_INTLB, TRUE, &infeasible, &tightened) );
3332 assert(tightened);
3333 assert(!infeasible);
3334
3335 ++(*nchgbds);
3336
3337 nonesmax = 2 * (int)(SCIPvarGetUbLocal(consdata->intvar) + 0.5) + (int) consdata->rhs; /*lint !e713*/
3338 }
3339
3340 assert(nvars - nfixedzeros >= nonesmin);
3341 assert(nfixedones <= nonesmax);
3342
3343 /* the number of variables that are free or fixed to 1 is exactly the minimum required -> fix free variables to 1 */
3344 if ( nvars - nfixedzeros == nonesmin )
3345 {
3346 SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 1 to reach lower bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmin);
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], TRUE, cons, (int)PROPRULE_INTLB, &infeasible, &tightened) );
3353 assert( !infeasible );
3354 assert( tightened );
3355
3356 ++(*nfixedvars);
3357 }
3358 }
3361
3362 return SCIP_OKAY;
3363 }
3364
3365 /* the number of variables that are fixed to 1 is exactly the maximum required -> fix free variables to 0 */
3366 if ( nfixedones == nonesmax )
3367 {
3368 SCIPdebugMsg(scip, "constraint <%s>: fix %d free variables to 0 to guarantee upper bound of %d\n", SCIPconsGetName(cons), nvars - nfixedzeros - nfixedones, nonesmax);
3369
3370 for (i = 0; i < nvars; ++i)
3371 {
3372 if ( SCIPvarGetLbLocal(vars[i]) < 0.5 && SCIPvarGetUbLocal(vars[i]) > 0.5 )
3373 {
3374 SCIP_CALL( SCIPinferBinvarCons(scip, vars[i], FALSE, cons, (int)PROPRULE_INTUB, &infeasible, &tightened) );
3375 assert(!infeasible);
3376 assert(tightened);
3377 ++(*nfixedvars);
3378 }
3379 }
3382
3383 return SCIP_OKAY;
3384 }
3385 }
3386 }
3387
3388 /* switch to the new watched variables */
3389 SCIP_CALL( consdataSwitchWatchedvars(scip, consdata, eventhdlr, watchedvar1, watchedvar2) );
3390
3391 /* mark the constraint propagated */
3392 consdata->propagated = TRUE;
3393
3394 return SCIP_OKAY;
3395}
3396
3397/** resolves a conflict on the given variable by supplying the variables needed for applying the corresponding
3398 * propagation rules (see propagateCons())
3399 */
3400static
3402 SCIP* scip, /**< SCIP data structure */
3403 SCIP_CONS* cons, /**< constraint that inferred the bound change */
3404 SCIP_VAR* infervar, /**< variable that was deduced */
3405 PROPRULE proprule, /**< propagation rule that deduced the value */
3406 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
3407 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
3408 )
3409{
3410 assert(result != NULL);
3411
3412 SCIPdebugMsg(scip, "resolving fixations according to rule %d\n", (int) proprule);
3413
3414 SCIP_CALL( addConflictBounds(scip, cons, infervar, bdchgidx, proprule) );
3415 *result = SCIP_SUCCESS;
3416
3417 return SCIP_OKAY;
3418}
3419
3420/** try to use clique information to delete a part of the xor constraint or even fix variables */
3421static
3423 SCIP* scip, /**< SCIP data structure */
3424 SCIP_CONS* cons, /**< constraint that inferred the bound change */
3425 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3426 int* nchgcoefs, /**< pointer to add up the number of deleted entries */
3427 int* ndelconss, /**< pointer to add up the number of deleted constraints */
3428 int* naddconss, /**< pointer to add up the number of added constraints */
3429 SCIP_Bool* cutoff /**< pointer to store TRUE, if the node can be cut off */
3430 )
3431{
3432 SCIP_CONSDATA* consdata;
3433 SCIP_VAR** vars;
3434 int nvars;
3435 SCIP_Bool breaked;
3436 SCIP_Bool restart;
3437 int posnotinclq1;
3438 int posnotinclq2;
3439 int v;
3440 int v1;
3441
3442 assert(scip != NULL);
3443 assert(cons != NULL);
3444 assert(nfixedvars != NULL);
3445 assert(nchgcoefs != NULL);
3446 assert(ndelconss != NULL);
3447 assert(naddconss != NULL);
3448 assert(cutoff != NULL);
3449
3450 /* propagation can only be applied, if we know all operator variables */
3451 if( SCIPconsIsModifiable(cons) )
3452 return SCIP_OKAY;
3453
3454 consdata = SCIPconsGetData(cons);
3455 assert(consdata != NULL);
3456
3457 vars = consdata->vars;
3458 nvars = consdata->nvars;
3459
3460 if( nvars < 3 )
3461 return SCIP_OKAY;
3462
3463 /* we cannot perform this steps if the integer variables in not artificial */
3464 if( !consdata->deleteintvar )
3465 return SCIP_OKAY;
3466
3467#ifdef SCIP_DISABLED_CODE
3468 /* try to evaluate if clique presolving should only be done multiple times when the constraint changed */
3469 if( !consdata->changed )
3470 return SCIP_OKAY;
3471#endif
3472
3473 /* @todo: if clique information would have saved the type of the clique, like <= 1, or == 1 we could do more
3474 * presolving like:
3475 *
3476 * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2) == 1) => xor(x3,x4) = 0
3477 * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) == 1) => (x4 = 0 and delete xor constraint)
3478 */
3479
3480 /* 1. we have only clique information "<=", so we can check if all variables are in the same clique
3481 *
3482 * (xor(x1,x2,x3) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 = 1 and delete old
3483 * xor-constraint)
3484 *
3485 * (xor(x1,x2,x3) = 0 and clique(x1,x2,x3) <= 1) => (fix all variables x1 = x2 = x3 = 0 and delete old xor-
3486 * constraint)
3487 */
3488
3489 /* 2. we have only clique information "<=", so we can check if all but one variable are in the same clique
3490 *
3491 * (xor(x1,x2,x3,x4) = 1 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + x4 = 1 and
3492 * delete old xor constraint)
3493 *
3494 * (xor(x1,x2,x3,x4) = 0 and clique(x1,x2,x3) <= 1) => (add set-partioning constraint x1 + x2 + x3 + ~x4 = 1 and
3495 * delete old xor constraint)
3496 */
3497
3498 posnotinclq1 = -1; /* index of variable that is possible not in the clique */
3499 posnotinclq2 = -1; /* index of variable that is possible not in the clique */
3500 breaked = FALSE;
3501 restart = FALSE;
3502
3503 v = nvars - 2;
3504 while( v >= 0 )
3505 {
3506 SCIP_VAR* var;
3507 SCIP_VAR* var1;
3508 SCIP_Bool value;
3509 SCIP_Bool value1;
3510
3512
3513 value = SCIPvarIsActive(vars[v]);
3514
3515 if( !value )
3516 var = SCIPvarGetNegationVar(vars[v]);
3517 else
3518 var = vars[v];
3519
3520 if( posnotinclq1 == v )
3521 {
3522 --v;
3523 continue;
3524 }
3525
3526 for( v1 = v+1; v1 < nvars; ++v1 )
3527 {
3528 if( posnotinclq1 == v1 )
3529 continue;
3530
3531 value1 = SCIPvarIsActive(vars[v1]);
3532
3533 if( !value1 )
3534 var1 = SCIPvarGetNegationVar(vars[v1]);
3535 else
3536 var1 = vars[v1];
3537
3538 if( !SCIPvarsHaveCommonClique(var, value, var1, value1, TRUE) )
3539 {
3540 /* if the position of the variable which is not in the clique with all other variables is not yet
3541 * initialized, than do now, one of both variables does not fit
3542 */
3543 if( posnotinclq1 == -1 )
3544 {
3545 posnotinclq1 = v;
3546 posnotinclq2 = v1;
3547 }
3548 else
3549 {
3550 /* no clique with exactly nvars-1 variables */
3551 if( restart || (posnotinclq2 != v && posnotinclq2 != v1) )
3552 {
3553 breaked = TRUE;
3554 break;
3555 }
3556
3557 /* check the second variables for not fitting into the clique of (nvars - 1) variables */
3558 posnotinclq1 = posnotinclq2;
3559 restart = TRUE;
3560 v = nvars - 1;
3561 }
3562
3563 break;
3564 }
3565 else
3566 assert(vars[v] != vars[v1]);
3567 }
3568
3569 if( breaked )
3570 break;
3571
3572 --v;
3573 }
3574
3575 /* at least nvars-1 variables are in one clique */
3576 if( !breaked ) /*lint !e774*/
3577 {
3578 /* all variables are in one clique, case 1 */
3579 if( posnotinclq1 == -1 )
3580 {
3581 /* all variables of xor constraints <%s> (with rhs == 1) are in one clique, so create a setpartitioning
3582 * constraint with all variables and delete this xor-constraint */
3583 if( consdata->rhs )
3584 {
3585 SCIP_CONS* newcons;
3586 char consname[SCIP_MAXSTRLEN];
3587
3588 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_complete_clq", SCIPconsGetName(cons));
3589 SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, nvars, vars,
3594
3595 SCIP_CALL( SCIPaddCons(scip, newcons) );
3596 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3597 SCIPdebug( SCIP_CALL( SCIPprintCons(scip, newcons, NULL) ) );
3598 ++(*naddconss);
3599
3600 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3601 }
3602 /* all variables of xor constraints <%s> (with rhs == 0) are in one clique, so fixed all variables to 0 */
3603 else
3604 {
3605 SCIP_Bool infeasible;
3606 SCIP_Bool fixed;
3607
3608 SCIPdebugMsg(scip, "all variables of xor constraints <%s> are in one clique, so fixed all variables to 0\n",
3609 SCIPconsGetName(cons));
3611
3612 for( v = nvars - 1; v >= 0; --v )
3613 {
3614 SCIPdebugMsg(scip, "fixing variable <%s> to 0\n", SCIPvarGetName(vars[v]));
3615 SCIP_CALL( SCIPfixVar(scip, vars[v], 0.0, &infeasible, &fixed) );
3616
3617 assert(infeasible || fixed);
3618
3619 if( infeasible )
3620 {
3621 *cutoff = infeasible;
3622
3623 return SCIP_OKAY;
3624 }
3625 else
3626 ++(*nfixedvars);
3627 }
3628 }
3629 }
3630 /* all but one variable are in one clique, case 2 */
3631 else
3632 {
3633 SCIP_CONS* newcons;
3634 char consname[SCIP_MAXSTRLEN];
3635
3636 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "%s_completed_clq", SCIPconsGetName(cons));
3637
3638 /* complete clique by creating a set partioning constraint over all variables */
3639
3640 /* if rhs == FALSE we need to exchange the variable not appaering in the clique with the negated variables */
3641 if( !consdata->rhs )
3642 {
3643 SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, 0, NULL,
3648
3649 for( v = 0; v < nvars; ++v )
3650 {
3651 if( v == posnotinclq1 )
3652 {
3653 SCIP_VAR* var;
3654
3655 SCIP_CALL( SCIPgetNegatedVar(scip, vars[v], &var) );
3656 assert(var != NULL);
3657
3658 SCIP_CALL( SCIPaddCoefSetppc(scip, newcons, var) );
3659 }
3660 else
3661 {
3662 SCIP_CALL( SCIPaddCoefSetppc(scip, newcons, vars[v]) );
3663 }
3664 }
3665 }
3666 /* if rhs == TRUE we can add all variables to the clique constraint directly */
3667 else
3668 {
3669 SCIP_CALL( SCIPcreateConsSetpart(scip, &newcons, consname, nvars, vars,
3674 }
3675
3676 SCIP_CALL( SCIPaddCons(scip, newcons) );
3677 SCIPdebugMsg(scip, "added a clique/setppc constraint <%s> \n", SCIPconsGetName(newcons));
3678 SCIPdebug( SCIP_CALL( SCIPprintCons(scip, newcons, NULL) ) );
3679 ++(*naddconss);
3680
3681 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
3682 }
3683
3684 /* fix integer variable if it exists */
3685 if( consdata->intvar != NULL )
3686 {
3687 SCIP_Bool infeasible;
3688 SCIP_Bool fixed;
3689
3690 SCIPdebugMsg(scip, "also fix the integer variable <%s> to 0\n", SCIPvarGetName(consdata->intvar));
3691 SCIP_CALL( SCIPfixVar(scip, consdata->intvar, 0.0, &infeasible, &fixed) );
3692
3693 assert(infeasible || fixed || SCIPvarGetStatus(consdata->intvar) == SCIP_VARSTATUS_FIXED);
3694
3695 if( infeasible )
3696 {
3697 *cutoff = infeasible;
3698 return SCIP_OKAY;
3699 }
3700 else if( fixed )
3701 ++(*nfixedvars);
3702 }
3703
3704 /* delete old redundant xor-constraint */
3705 SCIP_CALL( SCIPdelCons(scip, cons) );
3706 ++(*ndelconss);
3707 }
3708
3709 return SCIP_OKAY;
3710}
3711
3712/** compares each constraint with all other constraints for possible redundancy and removes or changes constraint
3713 * accordingly; in contrast to preprocessConstraintPairs(), it uses a hash table
3714 */
3715static
3717 SCIP* scip, /**< SCIP data structure */
3718 BMS_BLKMEM* blkmem, /**< block memory */
3719 SCIP_CONS** conss, /**< constraint set */
3720 int nconss, /**< number of constraints in constraint set */
3721 int* firstchange, /**< pointer to store first changed constraint */
3722 int* nchgcoefs, /**< pointer to add up the number of changed coefficients */
3723 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3724 int* naggrvars, /**< pointer to add up the number of aggregated variables */
3725 int* ndelconss, /**< pointer to count number of deleted constraints */
3726 int* naddconss, /**< pointer to count number of added constraints */
3727 SCIP_Bool* cutoff /**< pointer to store TRUE, if a cutoff was found */
3728 )
3729{
3730 SCIP_HASHTABLE* hashtable;
3731 int hashtablesize;
3732 int c;
3733
3734 assert(conss != NULL);
3735 assert(ndelconss != NULL);
3736
3737 /* create a hash table for the constraint set */
3738 hashtablesize = nconss;
3739 hashtablesize = MAX(hashtablesize, HASHSIZE_XORCONS);
3740
3741 SCIP_CALL( SCIPhashtableCreate(&hashtable, blkmem, hashtablesize,
3742 hashGetKeyXorcons, hashKeyEqXorcons, hashKeyValXorcons, (void*) scip) );
3743
3744 /* check all constraints in the given set for redundancy */
3745 for( c = 0; c < nconss; ++c )
3746 {
3747 SCIP_CONS* cons0;
3748 SCIP_CONS* cons1;
3749 SCIP_CONSDATA* consdata0;
3750 SCIP_CONSHDLR* conshdlr;
3751 SCIP_CONSHDLRDATA* conshdlrdata;
3752
3753 cons0 = conss[c];
3754
3755 if( !SCIPconsIsActive(cons0) || SCIPconsIsModifiable(cons0) )
3756 continue;
3757
3758 /* get constraint handler data */
3759 conshdlr = SCIPconsGetHdlr(cons0);
3760 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3761 assert(conshdlrdata != NULL);
3762
3763 /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3764 * variables inside so we need to remove them for sorting
3765 */
3766 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3767 * merge multiple entries of the same or negated variables
3768 */
3769 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3770 if( *cutoff )
3771 goto TERMINATE;
3772
3773 consdata0 = SCIPconsGetData(cons0);
3774
3775 assert(consdata0 != NULL);
3776
3777 /* applyFixings() led to an empty or trivial constraint */
3778 if( consdata0->nvars <= 1 )
3779 {
3780 if( consdata0->nvars == 0 )
3781 {
3782 /* the constraints activity cannot match an odd right hand side */
3783 if( consdata0->rhs )
3784 {
3785 *cutoff = TRUE;
3786 break;
3787 }
3788 }
3789 else
3790 {
3791 /* exactly 1 variable left. */
3792 SCIP_Bool infeasible;
3793 SCIP_Bool fixed;
3794
3795 /* fix remaining variable */
3796 SCIP_CALL( SCIPfixVar(scip, consdata0->vars[0], (SCIP_Real) consdata0->rhs, &infeasible, &fixed) );
3797 assert(!infeasible);
3798
3799 if( fixed )
3800 ++(*nfixedvars);
3801 }
3802
3803 /* fix integral variable if present */
3804 if( consdata0->intvar != NULL )
3805 {
3806 SCIP_Bool infeasible;
3807 SCIP_Bool fixed;
3808
3809 SCIP_CALL( SCIPfixVar(scip, consdata0->intvar, 0.0, &infeasible, &fixed) );
3810 assert(!infeasible);
3811
3812 if( fixed )
3813 ++(*nfixedvars);
3814 }
3815
3816 /* delete empty constraint */
3817 SCIP_CALL( SCIPdelCons(scip, cons0) );
3818 ++(*ndelconss);
3819
3820 continue;
3821 }
3822
3823 /* sort the constraint */
3824 consdataSort(consdata0);
3825 assert(consdata0->sorted);
3826
3827 /* get constraint from current hash table with same variables as cons0 */
3828 cons1 = (SCIP_CONS*)(SCIPhashtableRetrieve(hashtable, (void*)cons0));
3829
3830 if( cons1 != NULL )
3831 {
3832 SCIP_CONSDATA* consdata1;
3833
3834 assert(SCIPconsIsActive(cons1));
3835 assert(!SCIPconsIsModifiable(cons1));
3836
3837 consdata1 = SCIPconsGetData(cons1);
3838
3839 assert(consdata1 != NULL);
3840 assert(consdata0->nvars >= 1 && consdata0->nvars == consdata1->nvars);
3841
3842 assert(consdata0->sorted && consdata1->sorted);
3843 assert(consdata0->vars[0] == consdata1->vars[0]);
3844
3845 if( consdata0->rhs != consdata1->rhs )
3846 {
3847 *cutoff = TRUE;
3848 goto TERMINATE;
3849 }
3850
3851 /* aggregate parity variables into each other */
3852 if( consdata0->intvar != consdata1->intvar && consdata0->intvar != NULL )
3853 {
3854 if( consdata1->intvar != NULL )
3855 {
3856 SCIP_Bool redundant;
3857 SCIP_Bool aggregated;
3858 SCIP_Bool infeasible;
3859
3860 SCIP_CALL( SCIPaggregateVars(scip, consdata0->intvar, consdata1->intvar, 1.0, -1.0, 0.0, &infeasible, &redundant, &aggregated) );
3861
3862 if( aggregated )
3863 {
3864 ++(*naggrvars);
3865 }
3866 if( infeasible )
3867 {
3868 *cutoff = TRUE;
3869 goto TERMINATE;
3870 }
3871 }
3872 /* the special case that only cons0 has a parity variable 'intvar' is treated by swapping cons0 and cons1 */
3873 else
3874 {
3875 SCIP_CALL( SCIPhashtableInsert(hashtable, (void *)cons0) );
3876 assert(SCIPhashtableRetrieve(hashtable, (void *)cons1) == cons0);
3877
3878 SCIPswapPointers((void**)&cons0, (void**)(&cons1));
3879 SCIPswapPointers((void**)&consdata0, (void**)(&consdata1));
3880 }
3881 }
3882
3883 /* delete cons0 and update flags of cons1 s.t. nonredundant information doesn't get lost */
3884 /* coverity[swapped_arguments] */
3885 SCIP_CALL( SCIPupdateConsFlags(scip, cons1, cons0) );
3886 SCIP_CALL( SCIPdelCons(scip, cons0) );
3887 (*ndelconss)++;
3888
3889 /* update the first changed constraint to begin the next aggregation round with */
3890 if( consdata0->changed && SCIPconsGetPos(cons1) < *firstchange )
3891 *firstchange = SCIPconsGetPos(cons1);
3892
3893 assert(SCIPconsIsActive(cons1));
3894 }
3895 else
3896 {
3897 /* no such constraint in current hash table: insert cons0 into hash table */
3898 SCIP_CALL( SCIPhashtableInsert(hashtable, (void*) cons0) );
3899 }
3900 }
3901
3902 TERMINATE:
3903 /* free hash table */
3904 SCIPhashtableFree(&hashtable);
3905
3906 return SCIP_OKAY;
3907}
3908
3909/** compares constraint with all prior constraints for possible redundancy or aggregation,
3910 * and removes or changes constraint accordingly
3911 */
3912static
3914 SCIP* scip, /**< SCIP data structure */
3915 SCIP_CONS** conss, /**< constraint set */
3916 int firstchange, /**< first constraint that changed since last pair preprocessing round */
3917 int chkind, /**< index of constraint to check against all prior indices upto startind */
3918 SCIP_Bool* cutoff, /**< pointer to store TRUE, if a cutoff was found */
3919 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
3920 int* naggrvars, /**< pointer to count number of aggregated variables */
3921 int* ndelconss, /**< pointer to count number of deleted constraints */
3922 int* naddconss, /**< pointer to count number of added constraints */
3923 int* nchgcoefs /**< pointer to add up the number of changed coefficients */
3924 )
3925{
3926 SCIP_CONSHDLR* conshdlr;
3927 SCIP_CONSHDLRDATA* conshdlrdata;
3928 SCIP_CONS* cons0;
3929 SCIP_CONSDATA* consdata0;
3930 SCIP_Bool cons0changed;
3931 int c;
3932
3933 assert(conss != NULL);
3934 assert(firstchange <= chkind);
3935 assert(cutoff != NULL);
3936 assert(nfixedvars != NULL);
3937 assert(naggrvars != NULL);
3938 assert(ndelconss != NULL);
3939 assert(nchgcoefs != NULL);
3940
3941 /* get the constraint to be checked against all prior constraints */
3942 cons0 = conss[chkind];
3943 assert(SCIPconsIsActive(cons0));
3944 assert(!SCIPconsIsModifiable(cons0));
3945
3946 consdata0 = SCIPconsGetData(cons0);
3947 assert(consdata0 != NULL);
3948 assert(consdata0->nvars >= 1);
3949
3950 /* get constraint handler data */
3951 conshdlr = SCIPconsGetHdlr(cons0);
3952 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3953 assert(conshdlrdata != NULL);
3954
3955 /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
3956 * variables inside so we need to remove them for sorting
3957 */
3958 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
3959 * merge multiple entries of the same or negated variables
3960 */
3961 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
3962 if( *cutoff )
3963 return SCIP_OKAY;
3964
3965 /* sort cons0 */
3966 consdataSort(consdata0);
3967 assert(consdata0->sorted);
3968
3969 /* check constraint against all prior constraints */
3970 cons0changed = consdata0->changed;
3971 consdata0->changed = FALSE;
3972 for( c = (cons0changed ? 0 : firstchange); c < chkind && !(*cutoff) && SCIPconsIsActive(cons0) && !SCIPisStopped(scip); ++c )
3973 {
3974 SCIP_CONS* cons1;
3975 SCIP_CONSDATA* consdata1;
3976 SCIP_VAR* singlevar0;
3977 SCIP_VAR* singlevar1;
3978 SCIP_Bool parity;
3979 SCIP_Bool cons0hastwoothervars;
3980 SCIP_Bool cons1hastwoothervars;
3981 SCIP_Bool aborted;
3982 SCIP_Bool infeasible;
3983 SCIP_Bool fixed;
3984 SCIP_Bool redundant;
3985 SCIP_Bool aggregated;
3986 int v0;
3987 int v1;
3988
3989 cons1 = conss[c];
3990
3991 /* ignore inactive and modifiable constraints */
3992 if( !SCIPconsIsActive(cons1) || SCIPconsIsModifiable(cons1) )
3993 continue;
3994
3995 consdata1 = SCIPconsGetData(cons1);
3996 assert(consdata1 != NULL);
3997
3998 if( !consdata1->deleteintvar )
3999 continue;
4000
4001 /* it can happen that during preprocessing some variables got aggregated and a constraint now has not active
4002 * variables inside so we need to remove them for sorting
4003 */
4004 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
4005 * merge multiple entries of the same or negated variables
4006 */
4007 SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4008 assert(consdata1 == SCIPconsGetData(cons1));
4009 if( *cutoff )
4010 return SCIP_OKAY;
4011
4012 SCIPdebugMsg(scip, "preprocess xor constraint pair <%s>[chg:%u] and <%s>[chg:%u]\n",
4013 SCIPconsGetName(cons0), cons0changed, SCIPconsGetName(cons1), consdata1->changed);
4014
4015 /* if both constraints were not changed since last round, we can ignore the pair */
4016 if( !cons0changed && !consdata1->changed )
4017 continue;
4018
4019 /* applyFixings() led to an empty constraint */
4020 if( consdata1->nvars == 0 )
4021 {
4022 if( consdata1->rhs )
4023 {
4024 *cutoff = TRUE;
4025 break;
4026 }
4027 else
4028 {
4029 /* fix integral variable if present */
4030 if( consdata1->intvar != NULL )
4031 {
4032 SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
4033 assert(!infeasible);
4034 if( fixed )
4035 ++(*nfixedvars);
4036 }
4037
4038 /* delete empty constraint */
4039 SCIP_CALL( SCIPdelCons(scip, cons1) );
4040 ++(*ndelconss);
4041
4042 continue;
4043 }
4044 }
4045 else if( consdata1->nvars == 1 )
4046 {
4047 /* fix remaining variable */
4048 SCIP_CALL( SCIPfixVar(scip, consdata1->vars[0], (SCIP_Real) consdata1->rhs, &infeasible, &fixed) );
4049 assert(!infeasible);
4050
4051 if( fixed )
4052 ++(*nfixedvars);
4053
4054 /* fix integral variable if present */
4055 if( consdata1->intvar != NULL )
4056 {
4057 SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
4058 assert(!infeasible);
4059 if( fixed )
4060 ++(*nfixedvars);
4061 }
4062
4063 SCIP_CALL( SCIPdelCons(scip, cons1) );
4064 ++(*ndelconss);
4065
4066 /* check for fixed variable in cons0 and remove it */
4067 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4068 assert(!(*cutoff));
4069
4070 /* sort cons0 */
4071 consdataSort(consdata0);
4072 assert(consdata0->sorted);
4073
4074 continue;
4075 }
4076 else if( consdata1->nvars == 2 )
4077 {
4078 if( !(consdata1->rhs) )
4079 {
4080 /* aggregate var0 == var1 */
4081 SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, -1.0, 0.0,
4082 &infeasible, &redundant, &aggregated) );
4083 }
4084 else
4085 {
4086 /* aggregate var0 == 1 - var1 */
4087 SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->vars[1], 1.0, 1.0, 1.0,
4088 &infeasible, &redundant, &aggregated) );
4089 }
4090 assert(!infeasible);
4091 assert(redundant || SCIPdoNotAggr(scip));
4092
4093 if( aggregated )
4094 {
4095 ++(*naggrvars);
4096
4097 /* check for aggregated variable in cons0 and remove it */
4098 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4099 if( *cutoff )
4100 return SCIP_OKAY;
4101
4102 /* sort cons0 */
4103 consdataSort(consdata0);
4104 assert(consdata0->sorted);
4105 }
4106
4107 if( redundant )
4108 {
4109 /* fix or aggregate the intvar, if it exists */
4110 if( consdata1->intvar != NULL )
4111 {
4112 /* we have var0 + var1 - 2 * intvar = 1, and aggregated var1 = 1 - var0,
4113 * thus, intvar is always 0 */
4114 if( consdata1->rhs )
4115 {
4116 SCIP_CALL( SCIPfixVar(scip, consdata1->intvar, 0.0, &infeasible, &fixed) );
4117 assert(!infeasible);
4118 if( fixed )
4119 ++(*nfixedvars);
4120 }
4121 /* we have var0 + var1 - 2 * intvar = 0, and aggregated var1 = var0,
4122 * i.e., 2 * var0 - 2 * intvar = 0, so intvar = var0 holds and we aggregate */
4123 else
4124 {
4125 assert(!consdata1->rhs);
4126
4127 /* aggregate intvar == var0 */
4128 SCIP_CALL( SCIPaggregateVars(scip, consdata1->vars[0], consdata1->intvar, 1.0, -1.0, 0.0,
4129 &infeasible, &redundant, &aggregated) );
4130 assert(!infeasible);
4131 assert(redundant || SCIPdoNotAggr(scip));
4132
4133 if( aggregated )
4134 {
4135 ++(*naggrvars);
4136 }
4137 }
4138 }
4139
4140 if( redundant )
4141 {
4142 SCIP_CALL( SCIPdelCons(scip, cons1) );
4143 ++(*ndelconss);
4144 }
4145 }
4146
4147 continue;
4148 }
4149 assert(consdata0->sorted);
4150
4151 /* sort cons1 */
4152 consdataSort(consdata1);
4153 assert(consdata1->sorted);
4154
4155 /* check whether
4156 * (a) one problem variable set is a subset of the other, or
4157 * (b) the problem variable sets are almost equal with only one variable in each constraint that is not
4158 * member of the other
4159 */
4160 aborted = FALSE;
4161 parity = (consdata0->rhs ^ consdata1->rhs);
4162 cons0hastwoothervars = FALSE;
4163 cons1hastwoothervars = FALSE;
4164 singlevar0 = NULL;
4165 singlevar1 = NULL;
4166 v0 = 0;
4167 v1 = 0;
4168 while( (v0 < consdata0->nvars || v1 < consdata1->nvars) && !aborted )
4169 {
4170 int cmp;
4171
4172 assert(v0 <= consdata0->nvars);
4173 assert(v1 <= consdata1->nvars);
4174
4175 if( v0 == consdata0->nvars )
4176 cmp = +1;
4177 else if( v1 == consdata1->nvars )
4178 cmp = -1;
4179 else
4180 cmp = SCIPvarCompareActiveAndNegated(consdata0->vars[v0], consdata1->vars[v1]);
4181
4182 switch( cmp )
4183 {
4184 case -1:
4185 /* variable doesn't appear in cons1 */
4186 assert(v0 < consdata0->nvars);
4187 if( singlevar0 == NULL )
4188 {
4189 singlevar0 = consdata0->vars[v0];
4190 if( cons1hastwoothervars )
4191 aborted = TRUE;
4192 }
4193 else
4194 {
4195 cons0hastwoothervars = TRUE;
4196 if( singlevar1 != NULL )
4197 aborted = TRUE;
4198 }
4199 v0++;
4200 break;
4201
4202 case +1:
4203 /* variable doesn't appear in cons0 */
4204 assert(v1 < consdata1->nvars);
4205 if( singlevar1 == NULL )
4206 {
4207 singlevar1 = consdata1->vars[v1];
4208 if( cons0hastwoothervars )
4209 aborted = TRUE;
4210 }
4211 else
4212 {
4213 cons1hastwoothervars = TRUE;
4214 if( singlevar0 != NULL )
4215 aborted = TRUE;
4216 }
4217 v1++;
4218 break;
4219
4220 case 0:
4221 /* variable appears in both constraints */
4222 assert(v0 < consdata0->nvars);
4223 assert(v1 < consdata1->nvars);
4224 assert(SCIPvarGetProbvar(consdata0->vars[v0]) == SCIPvarGetProbvar(consdata1->vars[v1]));
4225 if( consdata0->vars[v0] != consdata1->vars[v1] )
4226 {
4227 assert(SCIPvarGetNegatedVar(consdata0->vars[v0]) == consdata1->vars[v1]);
4228 parity = !parity;
4229 }
4230 v0++;
4231 v1++;
4232 break;
4233
4234 default:
4235 SCIPerrorMessage("invalid comparison result\n");
4236 SCIPABORT();
4237 return SCIP_INVALIDDATA; /*lint !e527*/
4238 }
4239 }
4240
4241 /* check if a useful presolving is possible */
4242 if( (cons0hastwoothervars && singlevar1 != NULL) || (cons1hastwoothervars && singlevar0 != NULL) )
4243 continue;
4244
4245 /* check if one problem variable set is a subset of the other */
4246 if( singlevar0 == NULL && singlevar1 == NULL )
4247 {
4248 /* both constraints are equal */
4249 if( !parity )
4250 {
4251 /* even parity: constraints are redundant */
4252 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are redundant: delete <%s>\n",
4253 SCIPconsGetName(cons0), SCIPconsGetName(cons1), SCIPconsGetName(cons1));
4254 SCIPdebugPrintCons(scip, cons0, NULL);
4255 SCIPdebugPrintCons(scip, cons1, NULL);
4256
4257 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4258 SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4259 SCIP_CALL( SCIPdelCons(scip, cons1) );
4260 (*ndelconss)++;
4261
4262 if( consdata1->intvar != NULL )
4263 {
4264 /* need to update integer variable, consider the following case:
4265 * c1: xor(x1, x2, x3) = 1 (intvar1 = y1)
4266 * c2: xor(x1, x2, x3) = 1 (intvar0 = NULL or intvar0 = y0)
4267 *
4268 * if intvar0 = NULL we have to assign intvar0 = y1. otherwise, we have to ensure that y1 = y0 holds.
4269 * if aggregation is allowed, we can aggregate both variables. otherwise, we have to add a linear
4270 * constraint y1 - y0 = 0.
4271 */
4272 if( consdata0->intvar == NULL )
4273 {
4274 SCIP_CALL( setIntvar(scip, cons0, consdata1->intvar) );
4275 }
4276 else
4277 {
4278 /* aggregate integer variables */
4279 SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4280 &infeasible, &redundant, &aggregated) );
4281
4282 *cutoff = *cutoff || infeasible;
4283
4284 if( aggregated )
4285 {
4286 (*naggrvars)++;
4287 assert(SCIPvarIsActive(consdata0->intvar));
4288 }
4289 else
4290 {
4291 SCIP_CONS* newcons;
4292 char consname[SCIP_MAXSTRLEN];
4293 SCIP_VAR* newvars[2];
4294 SCIP_Real vals[2];
4295
4296 newvars[0] = consdata1->intvar;
4297 vals[0] = 1.0;
4298 newvars[1] = consdata0->intvar;
4299 vals[1] = -1.0;
4300
4301 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "agg_%s", SCIPconsGetName(cons1));
4302
4303 SCIP_CALL( SCIPcreateConsLinear(scip, &newcons, consname, 2, newvars, vals, 0.0, 0.0,
4304 SCIPconsIsInitial(cons1), SCIPconsIsSeparated(cons1), TRUE, /*SCIPconsIsEnforced(cons),*/
4305 TRUE, TRUE, /*SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),*/
4308
4309 SCIP_CALL( SCIPaddCons(scip, newcons) );
4310 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
4311 ++(*naddconss);
4312 }
4313 }
4314 }
4315 }
4316 else
4317 {
4318 /* odd parity: constraints are contradicting */
4319 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> are contradicting\n",
4320 SCIPconsGetName(cons0), SCIPconsGetName(cons1));
4321 SCIPdebugPrintCons(scip, cons0, NULL);
4322 SCIPdebugPrintCons(scip, cons1, NULL);
4323 *cutoff = TRUE;
4324 }
4325 }
4326 else if( singlevar1 == NULL )
4327 {
4328 /* cons1 is a subset of cons0 */
4329 if( !cons0hastwoothervars )
4330 {
4331 /* only one additional variable in cons0: fix this variable according to the parity */
4332 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4333 SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar0));
4334 SCIPdebugPrintCons(scip, cons0, NULL);
4335 SCIPdebugPrintCons(scip, cons1, NULL);
4336 SCIP_CALL( SCIPfixVar(scip, singlevar0, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4337 *cutoff = *cutoff || infeasible;
4338 if ( fixed )
4339 (*nfixedvars)++;
4340
4341 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4342 SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4343 SCIP_CALL( SCIPdelCons(scip, cons1) );
4344 (*ndelconss)++;
4345 }
4346 else
4347 {
4348 int v;
4349
4350 /* more than one additional variable in cons0: add cons1 to cons0, thus eliminating the equal variables */
4351 SCIPdebugMsg(scip, "xor constraint <%s> is superset of <%s> with parity %u\n",
4352 SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity);
4353 SCIPdebugPrintCons(scip, cons0, NULL);
4354 SCIPdebugPrintCons(scip, cons1, NULL);
4355 for( v = 0; v < consdata1->nvars; ++v )
4356 {
4357 SCIP_CALL( addCoef(scip, cons0, consdata1->vars[v]) );
4358 }
4359
4360 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4361 assert(SCIPconsGetData(cons0) == consdata0);
4362 assert(consdata0->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4363 }
4364
4365 if( *cutoff )
4366 return SCIP_OKAY;
4367
4368 consdataSort(consdata0);
4369 assert(consdata0->sorted);
4370 }
4371 else if( singlevar0 == NULL )
4372 {
4373 /* cons0 is a subset of cons1 */
4374 if( !cons1hastwoothervars )
4375 {
4376 /* only one additional variable in cons1: fix this variable according to the parity */
4377 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == <%s>\n",
4378 SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar1));
4379 SCIPdebugPrintCons(scip, cons0, NULL);
4380 SCIPdebugPrintCons(scip, cons1, NULL);
4381 SCIP_CALL( SCIPfixVar(scip, singlevar1, parity ? 1.0 : 0.0, &infeasible, &fixed) );
4382 assert(infeasible || fixed);
4383 *cutoff = *cutoff || infeasible;
4384 (*nfixedvars)++;
4385
4386 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4387 SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4388 SCIP_CALL( SCIPdelCons(scip, cons1) );
4389 (*ndelconss)++;
4390 }
4391 else
4392 {
4393 int v;
4394
4395 /* more than one additional variable in cons1: add cons0 to cons1, thus eliminating the equal variables */
4396 SCIPdebugMsg(scip, "xor constraint <%s> is subset of <%s> with parity %u\n",
4397 SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity);
4398 SCIPdebugPrintCons(scip, cons0, NULL);
4399 SCIPdebugPrintCons(scip, cons1, NULL);
4400 for( v = 0; v < consdata0->nvars; ++v )
4401 {
4402 SCIP_CALL( addCoef(scip, cons1, consdata0->vars[v]) );
4403 }
4404 SCIP_CALL( applyFixings(scip, cons1, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4405 assert(SCIPconsGetData(cons1) == consdata1);
4406 assert(consdata1->nvars >= 2); /* at least the two "other" variables should remain in the constraint */
4407
4408 if( *cutoff )
4409 return SCIP_OKAY;
4410
4411 consdataSort(consdata1);
4412 assert(consdata1->sorted);
4413 }
4414 }
4415 else
4416 {
4417 assert(!cons0hastwoothervars);
4418 assert(!cons1hastwoothervars);
4419
4420 /* sum of constraints is parity == singlevar0 xor singlevar1: aggregate variables and delete cons1 */
4421 SCIPdebugMsg(scip, "xor constraints <%s> and <%s> yield sum %u == xor(<%s>,<%s>)\n",
4422 SCIPconsGetName(cons0), SCIPconsGetName(cons1), parity, SCIPvarGetName(singlevar0),
4423 SCIPvarGetName(singlevar1));
4424 if( !parity )
4425 {
4426 /* aggregate singlevar0 == singlevar1 */
4427 SCIP_CALL( SCIPaggregateVars(scip, singlevar1, singlevar0, 1.0, -1.0, 0.0,
4428 &infeasible, &redundant, &aggregated) );
4429 }
4430 else
4431 {
4432 /* aggregate singlevar0 == 1-singlevar1 */
4433 SCIP_CALL( SCIPaggregateVars(scip, singlevar1, singlevar0, 1.0, 1.0, 1.0,
4434 &infeasible, &redundant, &aggregated) );
4435 }
4436 assert(infeasible || redundant || SCIPdoNotAggr(scip));
4437
4438 *cutoff = *cutoff || infeasible;
4439 if( aggregated )
4440 (*naggrvars)++;
4441
4442 if( redundant )
4443 {
4444 /* delete cons1 and update flags of cons0 s.t. nonredundant information doesn't get lost */
4445 SCIP_CALL( SCIPupdateConsFlags(scip, cons0, cons1) );
4446 SCIP_CALL( SCIPdelCons(scip, cons1) );
4447 (*ndelconss)++;
4448
4449 if( consdata1->intvar != NULL )
4450 {
4451 if( consdata0->intvar == NULL )
4452 {
4453 SCIP_CALL( setIntvar(scip, cons0, consdata0->intvar) );
4454 }
4455 else
4456 {
4457 /* aggregate integer variables */
4458 SCIP_CALL( SCIPaggregateVars(scip, consdata1->intvar, consdata0->intvar, 1.0, -1.0, 0.0,
4459 &infeasible, &redundant, &aggregated) );
4460
4461 *cutoff = *cutoff || infeasible;
4462 if( aggregated )
4463 (*naggrvars)++;
4464 }
4465 }
4466 }
4467
4468 if( !consdata0->sorted )
4469 consdataSort(consdata0);
4470 assert(consdata0->sorted);
4471
4472#ifdef SCIP_DISABLED_CODE
4473 /* TODO: consider running applyFixings() on the persistent constraint to detect a cutoff */
4474 /* remove all variables that are fixed to zero and all pairs of variables fixed to one;
4475 * merge multiple entries of the same or negated variables
4476 */
4477 SCIP_CALL( applyFixings(scip, cons0, conshdlrdata->eventhdlr, nchgcoefs, naggrvars, naddconss, cutoff) );
4478
4479 if( *cutoff )
4480 return SCIP_OKAY;
4481#endif
4482 }
4483 }
4484
4485 return SCIP_OKAY;
4486}
4487
4488/** creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs with a given artificial integer variable for the
4489 * linear relaxation
4490 *
4491 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
4492 */
4493static
4495 SCIP* scip, /**< SCIP data structure */
4496 SCIP_CONS** cons, /**< pointer to hold the created constraint */
4497 const char* name, /**< name of constraint */
4498 SCIP_Bool rhs, /**< right hand side of the constraint */
4499 int nvars, /**< number of operator variables in the constraint */
4500 SCIP_VAR** vars, /**< array with operator variables of constraint */
4501 SCIP_VAR* intvar, /**< artificial integer variable for linear relaxation */
4502 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
4503 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
4504 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
4505 * Usually set to TRUE. */
4506 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
4507 * TRUE for model constraints, FALSE for additional, redundant constraints. */
4508 SCIP_Bool check, /**< should the constraint be checked for feasibility?
4509 * TRUE for model constraints, FALSE for additional, redundant constraints. */
4510 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
4511 * Usually set to TRUE. */
4512 SCIP_Bool local, /**< is constraint only valid locally?
4513 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
4514 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
4515 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
4516 * adds coefficients to this constraint. */
4517 SCIP_Bool dynamic, /**< is constraint subject to aging?
4518 * Usually set to FALSE. Set to TRUE for own cuts which
4519 * are separated as constraints. */
4520 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
4521 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
4522 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
4523 * if it may be moved to a more global node?
4524 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
4525 )
4526{
4527 SCIP_CONSHDLR* conshdlr;
4528 SCIP_CONSDATA* consdata;
4529
4530 /* find the xor constraint handler */
4531 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
4532 if( conshdlr == NULL )
4533 {
4534 SCIPerrorMessage("xor constraint handler not found\n");
4535 return SCIP_PLUGINNOTFOUND;
4536 }
4537
4538 /* create constraint data */
4539 SCIP_CALL( consdataCreate(scip, &consdata, rhs, nvars, vars, intvar) );
4540
4541 /* create constraint */
4542 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
4543 local, modifiable, dynamic, removable, stickingatnode) );
4544
4545 return SCIP_OKAY;
4546}
4547
4548
4549
4550/*
4551 * Linear constraint upgrading
4552 */
4553
4554/** tries to upgrade a linear constraint into an xor constraint
4555 *
4556 * Assuming all variables are binary and have coefficients with an absolute value 1, except for an integer (or binary) variable
4557 * \f$z\f$ which has coefficient \f$a \in \{-2,2\}\f$ with absolute value 2 and appears only in this constraint,
4558 * we can transform:
4559 * \f[
4560 * \begin{array}{ll}
4561 * & -\sum_{i \in I} x_i + \sum_{j \in J} x_j + a \cdot z = r \\
4562 * \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j + a \cdot z = r + |I| \\
4563 * \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j - 2 \cdot y = (r + |I|) \text{ mod } 2,
4564 * \end{array}
4565 * \f]
4566 * where
4567 * \f[
4568 * y = \begin{cases}
4569 * \left\lfloor \frac{r + |I|}{2} \right\rfloor + z & \text{if }a = -2\\
4570 * \left\lfloor \frac{r + |I|}{2} \right\rfloor - z & \text{if }a = 2.
4571 * \end{cases}
4572 * \f]
4573 * 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
4574 * \frac{r + |I|}{2} \right\rfloor + \ell_z\f$ and \f$u_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor + u_z\f$.
4575 *
4576 * 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
4577 * \frac{r + |I|}{2} \right\rfloor - \ell_z\f$.
4578 *
4579 * Then consider the resulting XOR-constraint
4580 * \f[
4581 * \bigoplus_{i \in I} \bar{x}_i \oplus \bigoplus_{j \in j} x_j = (r + |I|) \text{ mod } 2.
4582 * \f]
4583 * 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
4584 * transformed constraint, otherwise it is a relaxation because the bounds on the \f$y\f$-variable may disallow
4585 * too many (or too few) operators set to 1. Therefore, the XOR constraint handler verifies in this case that the linear
4586 * equation holds, ie., that the \f$y\f$-variable has the correct value.
4587 */
4588static
4590{ /*lint --e{715}*/
4591 assert( upgdcons != NULL );
4592 assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 );
4593 assert( ! SCIPconsIsModifiable(cons) );
4594
4595 /* check, if linear constraint can be upgraded to xor constraint */
4596 /* @todo also applicable if the integer variable has a coefficient different from 2, e.g. a coefficient like 0.5 then
4597 * we could generate a new integer variable aggregated to the old one, possibly the constraint was then
4598 * normalized and all binary variables have coefficients of 2.0, if the coefficient is 4 then we need holes ...
4599 */
4600 if( integral && nposcont + nnegcont == 0 && nposbin + nnegbin + nposimplbin + nnegimplbin >= nvars-1 && ncoeffspone + ncoeffsnone == nvars-1 && ncoeffspint + ncoeffsnint == 1 )
4601 {
4602 assert( ncoeffspfrac + ncoeffsnfrac == 0 );
4603
4604 if ( SCIPisEQ(scip, lhs, rhs) && SCIPisIntegral(scip, lhs) )
4605 {
4606 SCIP_VAR** xorvars;
4607 SCIP_VAR* parityvar = NULL;
4608 SCIP_Bool postwo = FALSE;
4609 int cnt = 0;
4610 int j;
4611
4612 SCIP_CALL( SCIPallocBufferArray(scip, &xorvars, nvars) );
4613
4614 /* check parity of constraints */
4615 for( j = nvars - 1; j >= 0; --j )
4616 {
4617 if( SCIPisEQ(scip, REALABS(vals[j]), 2.0) )
4618 {
4619 parityvar = vars[j];
4620 postwo = (vals[j] > 0.0);
4621 }
4622 else if( !SCIPisEQ(scip, REALABS(vals[j]), 1.0) )
4623 break;
4624 else
4625 {
4626 /* exit if variable is not binary or implicit binary */
4627 if ( ! SCIPvarIsBinary(vars[j]) )
4628 {
4629 parityvar = NULL;
4630 break;
4631 }
4632
4633 /* need negated variables for correct propagation to the integer variable */
4634 if( vals[j] < 0.0 )
4635 {
4636 SCIP_CALL( SCIPgetNegatedVar(scip, vars[j], &(xorvars[cnt])) );
4637 assert(xorvars[cnt] != NULL);
4638 }
4639 else
4640 xorvars[cnt] = vars[j];
4641 ++cnt;
4642 }
4643 }
4644
4645 if( parityvar != NULL )
4646 {
4647 assert(cnt == nvars - 1);
4648
4649 /* check whether parity variable is present only in this constraint */
4650 if ( SCIPvarGetNLocksDownType(parityvar, SCIP_LOCKTYPE_MODEL) <= 1
4651 && SCIPvarGetNLocksUpType(parityvar, SCIP_LOCKTYPE_MODEL) <= 1 )
4652 {
4653 SCIP_VAR* intvar;
4654 SCIP_Bool rhsparity;
4655 SCIP_Bool neednew;
4656 int intrhs;
4657
4658 /* adjust the side, since we negated all binary variables with -1.0 as a coefficient */
4659 rhs += ncoeffsnone;
4660
4661 intrhs = (int) SCIPfloor(scip, rhs);
4662 rhsparity = ((SCIP_Bool) (intrhs % 2)); /*lint !e571*/
4663
4664 /* we need a new variable if the rhs is not 0 or 1 or if the coefficient was +2, since in these cases, we
4665 * need to aggregate the variables (flipping signs and/or shifting */
4666 if ( (intrhs != 1 && intrhs != 0) || postwo )
4667 neednew = TRUE;
4668 else
4669 neednew = FALSE;
4670
4671 /* check if we can use the parity variable as integer variable of the XOR constraint or do we need to
4672 * create a new variable and aggregate */
4673 if( neednew )
4674 {
4675 char varname[SCIP_MAXSTRLEN];
4676 SCIP_Real lb;
4677 SCIP_Real ub;
4678 SCIP_Bool isbinary;
4679 SCIP_Bool infeasible;
4680 SCIP_Bool redundant;
4681 SCIP_Bool aggregated;
4682 int intrhshalfed;
4683
4684 intrhshalfed = intrhs / 2;
4685
4686 if( postwo )
4687 {
4688 lb = intrhshalfed - SCIPvarGetUbGlobal(parityvar);
4689 ub = intrhshalfed - SCIPvarGetLbGlobal(parityvar);
4690 }
4691 else
4692 {
4693 lb = intrhshalfed + SCIPvarGetLbGlobal(parityvar);
4694 ub = intrhshalfed + SCIPvarGetUbGlobal(parityvar);
4695 }
4696 assert(SCIPisFeasLE(scip, lb, ub));
4697 assert(SCIPisFeasIntegral(scip, lb));
4698 assert(SCIPisFeasIntegral(scip, ub));
4699
4700 /* adjust bounds to be more integral */
4701 lb = SCIPfeasFloor(scip, lb);
4702 ub = SCIPfeasFloor(scip, ub);
4703
4704 isbinary = (SCIPisZero(scip, lb) && SCIPisEQ(scip, ub, 1.0));
4705
4706 /* something is wrong if parity variable is already binary, but artificial variable is not */
4707 if( SCIPvarIsBinary(parityvar) && !isbinary )
4708 {
4709 SCIPfreeBufferArray(scip, &xorvars);
4710 return SCIP_OKAY;
4711 }
4712
4713 (void) SCIPsnprintf(varname, SCIP_MAXSTRLEN, "%s_xor_upgr", SCIPvarGetName(parityvar));
4714 SCIP_CALL( SCIPcreateVar(scip, &intvar, varname, lb, ub, 0.0,
4716 SCIPvarIsInitial(parityvar), SCIPvarIsRemovable(parityvar), NULL, NULL, NULL, NULL, NULL) );
4717 SCIP_CALL( SCIPaddVar(scip, intvar) );
4718
4719 SCIPdebugMsg(scip, "created new variable for aggregation:");
4720 SCIPdebug( SCIPprintVar(scip, intvar, NULL) );
4721
4722 SCIP_CALL( SCIPaggregateVars(scip, parityvar, intvar, 1.0, postwo ? 1.0 : -1.0,
4723 (SCIP_Real) (postwo ? intrhshalfed : -intrhshalfed), &infeasible, &redundant, &aggregated) );
4724 assert(!infeasible);
4725
4726 /* maybe aggregation was forbidden, than we cannot upgrade this constraint */
4727 if( !aggregated )
4728 {
4729 SCIPfreeBufferArray(scip, &xorvars);
4730 return SCIP_OKAY;
4731 }
4732
4733 assert(redundant);
4734 assert(SCIPvarIsActive(intvar));
4735
4736#ifdef SCIP_DEBUG
4738 {
4739 SCIPdebugMsg(scip, "aggregated: <%s> = %g * <%s> + %g\n", SCIPvarGetName(parityvar),
4741 SCIPvarGetAggrConstant(parityvar));
4742 }
4743 else
4744 {
4745 assert( SCIPvarGetStatus(parityvar) == SCIP_VARSTATUS_NEGATED );
4746 SCIPdebugMsg(scip, "negated: <%s> = 1 - <%s>\n", SCIPvarGetName(parityvar),
4748 }
4749#endif
4750 }
4751 else
4752 intvar = parityvar;
4753
4754 assert(intvar != NULL);
4755
4756 SCIP_CALL( createConsXorIntvar(scip, upgdcons, SCIPconsGetName(cons), rhsparity, nvars - 1, xorvars, intvar,
4761
4762 SCIPdebugMsg(scip, "upgraded constraint <%s> to XOR constraint:\n", SCIPconsGetName(cons));
4763 SCIPdebugPrintCons(scip, *upgdcons, NULL);
4764
4765 if( neednew )
4766 {
4767 assert(intvar != parityvar);
4768 SCIP_CALL( SCIPreleaseVar(scip, &intvar) );
4769 }
4770 }
4771 }
4772
4773 SCIPfreeBufferArray(scip, &xorvars);
4774 }
4775 }
4776
4777 return SCIP_OKAY;
4778}
4779
4780/** adds symmetry information of constraint to a symmetry detection graph */
4781static
4783 SCIP* scip, /**< SCIP pointer */
4784 SYM_SYMTYPE symtype, /**< type of symmetries that need to be added */
4785 SCIP_CONS* cons, /**< constraint */
4786 SYM_GRAPH* graph, /**< symmetry detection graph */
4787 SCIP_Bool* success /**< pointer to store whether symmetry information could be added */
4788 )
4789{
4790 SCIP_VAR** xorvars;
4791 SCIP_VAR** vars;
4792 SCIP_Real* vals;
4793 SCIP_Real constant = 0.0;
4794 SCIP_Real lrhs;
4795 int nlocvars;
4796 int nvars;
4797 int i;
4798
4799 assert(scip != NULL);
4800 assert(cons != NULL);
4801 assert(graph != NULL);
4802 assert(success != NULL);
4803
4804 /* get active variables of the constraint */
4805 nvars = SCIPgetNVars(scip);
4806 nlocvars = SCIPgetNVarsXor(scip, cons);
4807
4808 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
4809 SCIP_CALL( SCIPallocBufferArray(scip, &vals, nvars) );
4810
4811 xorvars = SCIPgetVarsXor(scip, cons);
4812 for( i = 0; i < nlocvars; ++i )
4813 {
4814 vars[i] = xorvars[i];
4815 vals[i] = 1.0;
4816 }
4817
4818 if( SCIPgetIntVarXor(scip, cons) != NULL )
4819 {
4820 vars[nlocvars] = SCIPgetIntVarXor(scip, cons);
4821 vals[nlocvars++] = 2.0;
4822 }
4823 assert(nlocvars <= nvars);
4824
4825 SCIP_CALL( SCIPgetSymActiveVariables(scip, symtype, &vars, &vals, &nlocvars, &constant, SCIPisTransformed(scip)) );
4826 lrhs = (SCIP_Real) SCIPgetRhsXor(scip, cons) - constant;
4827
4828 SCIP_CALL( SCIPextendPermsymDetectionGraphLinear(scip, graph, vars, vals, nlocvars,
4829 cons, lrhs, lrhs, success) );
4830
4831 SCIPfreeBufferArray(scip, &vals);
4832 SCIPfreeBufferArray(scip, &vars);
4833
4834 return SCIP_OKAY;
4835}
4836
4837/*
4838 * Callback methods of constraint handler
4839 */
4840
4841/** copy method for constraint handler plugins (called when SCIP copies plugins) */
4842static
4844{ /*lint --e{715}*/
4845 assert(scip != NULL);
4846 assert(conshdlr != NULL);
4847 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
4848
4849 /* call inclusion method of constraint handler */
4851
4852 *valid = TRUE;
4853
4854 return SCIP_OKAY;
4855}
4856
4857/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
4858static
4860{ /*lint --e{715}*/
4861 SCIP_CONSHDLRDATA* conshdlrdata;
4862
4863 /* free constraint handler data */
4864 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4865 assert(conshdlrdata != NULL);
4866
4867 conshdlrdataFree(scip, &conshdlrdata);
4868
4869 SCIPconshdlrSetData(conshdlr, NULL);
4870
4871 return SCIP_OKAY;
4872}
4873
4874/** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
4875static
4877{ /*lint --e{715}*/
4878 SCIP_CONSDATA* consdata;
4879 int c;
4880
4881 /* release and free the rows of all constraints */
4882 for( c = 0; c < nconss; ++c )
4883 {
4884 consdata = SCIPconsGetData(conss[c]);
4885 SCIP_CALL( consdataFreeRows(scip, consdata) );
4886 }
4887
4888 return SCIP_OKAY;
4889}
4890
4891
4892/** frees specific constraint data */
4893static
4895{ /*lint --e{715}*/
4896 SCIP_CONSHDLRDATA* conshdlrdata;
4897
4898 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4899 assert(conshdlrdata != NULL);
4900
4902 {
4903 int v;
4904
4905 for( v = (*consdata)->nvars - 1; v >= 0; --v )
4906 {
4907 SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->vars[v], SCIP_EVENTTYPE_VARFIXED, conshdlrdata->eventhdlr,
4908 (SCIP_EVENTDATA*)(*consdata), -1) );
4909 }
4910 }
4911
4912 SCIP_CALL( consdataFree(scip, consdata, conshdlrdata->eventhdlr) );
4913
4914 return SCIP_OKAY;
4915}
4916
4917
4918/** transforms constraint data into data belonging to the transformed problem */
4919static
4921{ /*lint --e{715}*/
4922 SCIP_CONSDATA* sourcedata;
4923 SCIP_CONSDATA* targetdata;
4924
4925 sourcedata = SCIPconsGetData(sourcecons);
4926 assert(sourcedata != NULL);
4927 assert(sourcedata->nvars >= 1);
4928 assert(sourcedata->vars != NULL);
4929
4930 /* create target constraint data */
4931 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->rhs, sourcedata->nvars, sourcedata->vars, sourcedata->intvar) );
4932
4933 /* create target constraint */
4934 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
4935 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
4936 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
4937 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
4938 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
4939
4940 return SCIP_OKAY;
4941}
4942
4943
4944/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
4945static
4947{ /*lint --e{715}*/
4948 int i;
4949
4950 assert(infeasible != NULL);
4951
4952 *infeasible = FALSE;
4953
4954 for( i = 0; i < nconss && !(*infeasible); i++ )
4955 {
4956 assert(SCIPconsIsInitial(conss[i]));
4957 SCIP_CALL( addRelaxation(scip, conss[i], infeasible) );
4958 }
4959
4960 return SCIP_OKAY;
4961}
4962
4963
4964/** separation method of constraint handler for LP solutions */
4965static
4967{ /*lint --e{715}*/
4968 SCIP_CONSHDLRDATA* conshdlrdata;
4969 SCIP_Bool separated;
4970 SCIP_Bool cutoff;
4971 int c;
4972
4973 *result = SCIP_DIDNOTFIND;
4974
4975 conshdlrdata = SCIPconshdlrGetData(conshdlr);
4976 assert( conshdlrdata != NULL );
4977
4978 /* separate all useful constraints */
4979 for( c = 0; c < nusefulconss; ++c )
4980 {
4981 SCIP_CALL( separateCons(scip, conss[c], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
4982 if ( cutoff )
4983 *result = SCIP_CUTOFF;
4984 else if ( separated )
4985 *result = SCIP_SEPARATED;
4986 }
4987
4988 /* combine constraints to get more cuts */
4989 /**@todo combine constraints to get further cuts */
4990
4991 return SCIP_OKAY;
4992}
4993
4994
4995/** separation method of constraint handler for arbitrary primal solutions */
4996static
4998{ /*lint --e{715}*/
4999 SCIP_CONSHDLRDATA* conshdlrdata;
5000 SCIP_Bool separated;
5001 SCIP_Bool cutoff;
5002 int c;
5003
5004 *result = SCIP_DIDNOTFIND;
5005
5006 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5007 assert( conshdlrdata != NULL );
5008
5009 /* separate all useful constraints */
5010 for( c = 0; c < nusefulconss; ++c )
5011 {
5012 SCIP_CALL( separateCons(scip, conss[c], sol, conshdlrdata->separateparity, &separated, &cutoff) );
5013 if ( cutoff )
5014 *result = SCIP_CUTOFF;
5015 else if ( separated )
5016 *result = SCIP_SEPARATED;
5017 }
5018
5019 /* combine constraints to get more cuts */
5020 /**@todo combine constraints to get further cuts */
5021
5022 return SCIP_OKAY;
5023}
5024
5025
5026/** constraint enforcing method of constraint handler for LP solutions */
5027static
5029{ /*lint --e{715}*/
5030 SCIP_CONSHDLRDATA* conshdlrdata;
5031 SCIP_Bool violated;
5032 SCIP_Bool cutoff;
5033 int i;
5034
5035 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5036 assert( conshdlrdata != NULL );
5037
5038 /* method is called only for integral solutions, because the enforcing priority is negative */
5039 for( i = 0; i < nconss; i++ )
5040 {
5041 SCIP_CALL( checkCons(scip, conss[i], NULL, FALSE, FALSE, &violated) );
5042 if( violated )
5043 {
5044 SCIP_Bool separated;
5045
5046 SCIP_CALL( separateCons(scip, conss[i], NULL, conshdlrdata->separateparity, &separated, &cutoff) );
5047 if ( cutoff )
5048 *result = SCIP_CUTOFF;
5049 else
5050 {
5051 assert(separated); /* because the solution is integral, the separation always finds a cut */
5052 *result = SCIP_SEPARATED;
5053 }
5054 return SCIP_OKAY;
5055 }
5056 }
5057 *result = SCIP_FEASIBLE;
5058
5059 return SCIP_OKAY;
5060}
5061
5062
5063/** constraint enforcing method of constraint handler for relaxation solutions */
5064static
5066{ /*lint --e{715}*/
5067 SCIP_CONSHDLRDATA* conshdlrdata;
5068 SCIP_Bool violated;
5069 SCIP_Bool cutoff;
5070 int i;
5071
5072 conshdlrdata = SCIPconshdlrGetData(conshdlr);
5073 assert( conshdlrdata != NULL );
5074
5075 /* method is called only for integral solutions, because the enforcing priority is negative */
5076 for( i = 0; i < nconss; i++ )
5077 {
5078 SCIP_CALL( checkCons(scip, conss[i], sol, FALSE, FALSE, &violated) );
5079 if( violated )
5080 {
5081 SCIP_Bool separated;
5082
5083 SCIP_CALL( separateCons(scip, conss[i], sol, conshdlrdata->separateparity, &separated, &cutoff) );
5084 if ( cutoff )
5085 *result = SCIP_CUTOFF;
5086 else
5087 {
5088 assert(separated); /* because the solution is integral, the separation always finds a cut */
5089 *result = SCIP_SEPARATED;
5090 }
5091 return SCIP_OKAY;
5092 }
5093 }
5094 *result = SCIP_FEASIBLE;
5095
5096 return SCIP_OKAY;
5097}
5098
5099
5100/** constraint enforcing method of constraint handler for pseudo solutions */
5101static
5103{ /*lint --e{715}*/
5104 SCIP_Bool violated;
5105 int i;
5106
5107 /* method is called only for integral solutions, because the enforcing priority is negative */
5108 for( i = 0; i < nconss; i++ )
5109 {
5110 SCIP_CALL( checkCons(scip, conss[i], NULL, TRUE, FALSE, &violated) );
5111 if( violated )
5112 {
5113 *result = SCIP_INFEASIBLE;