Scippy

SCIP

Solving Constraint Integer Programs

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