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