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