SCIP
Solving Constraint Integer Programs
cons_xor.c File Reference
Detailed Description
Constraint handler for "xor" constraints, \(rhs = x_1 \oplus x_2 \oplus \dots \oplus x_n\).
This constraint handler deals with "xor" constraint. These are constraint of the form:
\[ rhs = x_1 \oplus x_2 \oplus \dots \oplus x_n \]
where \(x_i\) is a binary variable for all \(i\) and \(rhs\) is bool. The variables \(x\)'s are called operators. This constraint is satisfied if \(rhs\) is TRUE and an odd number of the operators are TRUE or if the \(rhs\) is FALSE and a even number of operators are TRUE. Hence, if the sum of \(rhs\) and operators is even.
Definition in file cons_xor.c.
#include "blockmemshell/memory.h"#include "scip/cons_linear.h"#include "scip/cons_setppc.h"#include "scip/cons_xor.h"#include "scip/debug.h"#include "scip/heur_trysol.h"#include "scip/pub_cons.h"#include "scip/pub_event.h"#include "scip/pub_lp.h"#include "scip/pub_message.h"#include "scip/pub_misc.h"#include "scip/pub_misc_sort.h"#include "scip/pub_var.h"#include "scip/scip_conflict.h"#include "scip/scip_cons.h"#include "scip/scip_copy.h"#include "scip/scip_cut.h"#include "scip/scip_event.h"#include "scip/scip_general.h"#include "scip/scip_heur.h"#include "scip/scip_lp.h"#include "scip/scip_mem.h"#include "scip/scip_message.h"#include "scip/scip_numerics.h"#include "scip/scip_param.h"#include "scip/scip_prob.h"#include "scip/scip_probing.h"#include "scip/scip_sol.h"#include "scip/scip_tree.h"#include "scip/scip_var.h"Go to the source code of this file.
Typedefs | |
| typedef unsigned short | Type |
| typedef enum Proprule | PROPRULE |
Enumerations | |
| enum | Proprule { PROPRULE_INVALID = 0, PROPRULE_1 = 1, PROPRULE_2 = 2, PROPRULE_3 = 3, PROPRULE_4 = 4, PROPRULE_0_INVALID = 0, PROPRULE_1_CORETIMES = 1, PROPRULE_2_EDGEFINDING = 2, PROPRULE_3_TTEF = 3, PROPRULE_1_RHS = 1, PROPRULE_1_LHS = 2, PROPRULE_1_RANGEDROW = 3, PROPRULE_INVALID = 0, PROPRULE_1 = 0, PROPRULE_2 = 1, PROPRULE_3 = 2, PROPRULE_4 = 3, PROPRULE_INVALID = 4, PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_0, PROPRULE_1, PROPRULE_INTLB, PROPRULE_INTUB, PROPRULE_INVALID } |
Functions | |
| static SCIP_RETCODE | lockRounding (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) |
| static SCIP_RETCODE | unlockRounding (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) |
| static SCIP_RETCODE | conshdlrdataCreate (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata, SCIP_EVENTHDLR *eventhdlr) |
| static void | conshdlrdataFree (SCIP *scip, SCIP_CONSHDLRDATA **conshdlrdata) |
| static SCIP_RETCODE | consdataSwitchWatchedvars (SCIP *scip, SCIP_CONSDATA *consdata, SCIP_EVENTHDLR *eventhdlr, int watchedvar1, int watchedvar2) |
| static SCIP_RETCODE | consdataEnsureVarsSize (SCIP *scip, SCIP_CONSDATA *consdata, int num) |
| static SCIP_RETCODE | consdataCreate (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_Bool rhs, int nvars, SCIP_VAR **vars, SCIP_VAR *intvar) |
| static SCIP_RETCODE | consdataFreeRows (SCIP *scip, SCIP_CONSDATA *consdata) |
| static SCIP_RETCODE | consdataFree (SCIP *scip, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlr) |
| static SCIP_RETCODE | consdataPrint (SCIP *scip, SCIP_CONSDATA *consdata, FILE *file, SCIP_Bool endline) |
| static SCIP_RETCODE | setIntvar (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) |
| static SCIP_RETCODE | addCoef (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var) |
| static SCIP_RETCODE | delCoefPos (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int pos) |
| static void | consdataSort (SCIP_CONSDATA *consdata) |
| static | SCIP_DECL_HASHGETKEY (hashGetKeyXorcons) |
| static | SCIP_DECL_HASHKEYEQ (hashKeyEqXorcons) |
| static | SCIP_DECL_HASHKEYVAL (hashKeyValXorcons) |
| static SCIP_RETCODE | applyFixings (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, int *nchgcoefs, int *naggrvars, int *naddconss, SCIP_Bool *cutoff) |
| static SCIP_RETCODE | addExtendedFlowFormulation (SCIP *scip, SCIP_CONS *cons, int *naggrvars, int *naddedconss) |
| static SCIP_RETCODE | addExtendedAsymmetricFormulation (SCIP *scip, SCIP_CONS *cons, int *naggrvars, int *naddedconss) |
| static SCIP_RETCODE | createRelaxation (SCIP *scip, SCIP_CONS *cons) |
| static SCIP_RETCODE | addRelaxation (SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible) |
| static SCIP_Bool | allRowsInLP (SCIP_CONSDATA *consdata) |
| static SCIP_RETCODE | checkCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool checklprows, SCIP_Bool *violated) |
| static SCIP_RETCODE | separateCons (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool separateparity, SCIP_Bool *separated, SCIP_Bool *cutoff) |
| static int | computeRowEchelonGF2 (SCIP *scip, int m, int n, int *p, int *s, Type **A, Type *b) |
| static void | solveRowEchelonGF2 (int m, int n, int r, int *p, int *s, Type **A, Type *b, Type *x) |
| static SCIP_RETCODE | checkSystemGF2 (SCIP *scip, SCIP_CONS **conss, int nconss, SCIP_SOL *currentsol, SCIP_RESULT *result) |
| static SCIP_RETCODE | addConflictBounds (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, SCIP_BDCHGIDX *bdchgidx, PROPRULE proprule) |
| static SCIP_RETCODE | analyzeConflict (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule) |
| static SCIP_RETCODE | propagateCons (SCIP *scip, SCIP_CONS *cons, SCIP_EVENTHDLR *eventhdlr, SCIP_Bool *cutoff, int *nfixedvars, int *nchgbds) |
| static SCIP_RETCODE | resolvePropagation (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, PROPRULE proprule, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result) |
| static SCIP_RETCODE | cliquePresolve (SCIP *scip, SCIP_CONS *cons, int *nfixedvars, int *nchgcoefs, int *ndelconss, int *naddconss, SCIP_Bool *cutoff) |
| 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) |
| 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) |
| 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) |
| static | SCIP_DECL_LINCONSUPGD (linconsUpgdXor) |
| static | SCIP_DECL_CONSHDLRCOPY (conshdlrCopyXor) |
| static | SCIP_DECL_CONSFREE (consFreeXor) |
| static | SCIP_DECL_CONSEXITSOL (consExitsolXor) |
| static | SCIP_DECL_CONSDELETE (consDeleteXor) |
| static | SCIP_DECL_CONSTRANS (consTransXor) |
| static | SCIP_DECL_CONSINITLP (consInitlpXor) |
| static | SCIP_DECL_CONSSEPALP (consSepalpXor) |
| static | SCIP_DECL_CONSSEPASOL (consSepasolXor) |
| static | SCIP_DECL_CONSENFOLP (consEnfolpXor) |
| static | SCIP_DECL_CONSENFORELAX (consEnforelaxXor) |
| static | SCIP_DECL_CONSENFOPS (consEnfopsXor) |
| static | SCIP_DECL_CONSCHECK (consCheckXor) |
| static | SCIP_DECL_CONSPROP (consPropXor) |
| static | SCIP_DECL_CONSINITPRE (consInitpreXor) |
| static | SCIP_DECL_CONSEXITPRE (consExitpreXor) |
| static | SCIP_DECL_CONSPRESOL (consPresolXor) |
| static | SCIP_DECL_CONSRESPROP (consRespropXor) |
| static | SCIP_DECL_CONSLOCK (consLockXor) |
| static | SCIP_DECL_CONSPRINT (consPrintXor) |
| static | SCIP_DECL_CONSCOPY (consCopyXor) |
| static | SCIP_DECL_CONSPARSE (consParseXor) |
| static | SCIP_DECL_CONSGETVARS (consGetVarsXor) |
| static | SCIP_DECL_CONSGETNVARS (consGetNVarsXor) |
| static | SCIP_DECL_EVENTEXEC (eventExecXor) |
| SCIP_RETCODE | SCIPincludeConshdlrXor (SCIP *scip) |
| 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) |
| SCIP_RETCODE | SCIPcreateConsBasicXor (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_Bool rhs, int nvars, SCIP_VAR **vars) |
| int | SCIPgetNVarsXor (SCIP *scip, SCIP_CONS *cons) |
| SCIP_VAR ** | SCIPgetVarsXor (SCIP *scip, SCIP_CONS *cons) |
| SCIP_VAR * | SCIPgetIntVarXor (SCIP *scip, SCIP_CONS *cons) |
| SCIP_Bool | SCIPgetRhsXor (SCIP *scip, SCIP_CONS *cons) |
Macro Definition Documentation
◆ CONSHDLR_NAME
| #define CONSHDLR_NAME "xor" |
Definition at line 87 of file cons_xor.c.
Referenced by addCoef(), consdataCreate(), createConsXorIntvar(), SCIP_DECL_CONSHDLRCOPY(), SCIPcreateConsXor(), SCIPgetIntVarXor(), SCIPgetNVarsXor(), SCIPgetRhsXor(), SCIPgetVarsXor(), and SCIPincludeConshdlrXor().
◆ CONSHDLR_DESC
| #define CONSHDLR_DESC "constraint handler for xor constraints: r = xor(x1, ..., xn)" |
Definition at line 88 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_SEPAPRIORITY
| #define CONSHDLR_SEPAPRIORITY +850200 |
priority of the constraint handler for separation
Definition at line 89 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_ENFOPRIORITY
| #define CONSHDLR_ENFOPRIORITY -850200 |
priority of the constraint handler for constraint enforcing
Definition at line 90 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_CHECKPRIORITY
| #define CONSHDLR_CHECKPRIORITY -850200 |
priority of the constraint handler for checking feasibility
Definition at line 91 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_SEPAFREQ
| #define CONSHDLR_SEPAFREQ 0 |
frequency for separating cuts; zero means to separate only in the root node
Definition at line 92 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_PROPFREQ
| #define CONSHDLR_PROPFREQ 1 |
frequency for propagating domains; zero means only preprocessing propagation
Definition at line 93 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_EAGERFREQ
| #define CONSHDLR_EAGERFREQ 100 |
frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only
Definition at line 94 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_MAXPREROUNDS
| #define CONSHDLR_MAXPREROUNDS -1 |
maximal number of presolving rounds the constraint handler participates in (-1: no limit)
Definition at line 97 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_DELAYSEPA
| #define CONSHDLR_DELAYSEPA FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 98 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_DELAYPROP
| #define CONSHDLR_DELAYPROP FALSE |
should propagation method be delayed, if other propagators found reductions?
Definition at line 99 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_NEEDSCONS
| #define CONSHDLR_NEEDSCONS TRUE |
should the constraint handler be skipped, if no constraints are available?
Definition at line 100 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_PROP_TIMING
| #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP |
Definition at line 102 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ CONSHDLR_PRESOLTIMING
| #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS |
Definition at line 103 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ EVENTHDLR_NAME
| #define EVENTHDLR_NAME "xor" |
Definition at line 105 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ EVENTHDLR_DESC
| #define EVENTHDLR_DESC "event handler for xor constraints" |
Definition at line 106 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ LINCONSUPGD_PRIORITY
| #define LINCONSUPGD_PRIORITY +600000 |
priority of the constraint handler for upgrading of linear constraints
Definition at line 108 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ DEFAULT_PRESOLPAIRWISE
| #define DEFAULT_PRESOLPAIRWISE TRUE |
should pairwise constraint comparison be performed in presolving?
Definition at line 110 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ DEFAULT_ADDEXTENDEDFORM
| #define DEFAULT_ADDEXTENDEDFORM FALSE |
should the extended formulation be added in presolving?
Definition at line 111 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ DEFAULT_ADDFLOWEXTENDED
| #define DEFAULT_ADDFLOWEXTENDED FALSE |
should the extended flow formulation be added (nonsymmetric formulation otherwise)?
Definition at line 112 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ DEFAULT_SEPARATEPARITY
| #define DEFAULT_SEPARATEPARITY FALSE |
should parity inequalities be separated?
Definition at line 113 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ DEFAULT_GAUSSPROPFREQ
| #define DEFAULT_GAUSSPROPFREQ 5 |
frequency for applying the Gauss propagator
Definition at line 114 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ HASHSIZE_XORCONS
| #define HASHSIZE_XORCONS 500 |
minimal size of hash table in logicor constraint tables
Definition at line 115 of file cons_xor.c.
Referenced by detectRedundantConstraints().
◆ DEFAULT_PRESOLUSEHASHING
| #define DEFAULT_PRESOLUSEHASHING TRUE |
should hash table be used for detecting redundant constraints in advance
Definition at line 116 of file cons_xor.c.
Referenced by SCIPincludeConshdlrXor().
◆ NMINCOMPARISONS
| #define NMINCOMPARISONS 200000 |
number for minimal pairwise presolving comparisons
Definition at line 117 of file cons_xor.c.
Referenced by SCIP_DECL_CONSPRESOL().
◆ MINGAINPERNMINCOMPARISONS
| #define MINGAINPERNMINCOMPARISONS 1e-06 |
minimal gain per minimal pairwise presolving comparisons to repeat pairwise comparison round
Definition at line 118 of file cons_xor.c.
Referenced by SCIP_DECL_CONSPRESOL().
◆ MAXXORCONSSSYSTEM
| #define MAXXORCONSSSYSTEM 1000 |
maximal number of active constraints for which checking the system over GF2 is performed
Definition at line 119 of file cons_xor.c.
Referenced by checkSystemGF2().
◆ MAXXORVARSSYSTEM
| #define MAXXORVARSSYSTEM 1000 |
maximal number of variables in xor constraints for which checking the system over GF2 is performed
Definition at line 120 of file cons_xor.c.
Referenced by checkSystemGF2().
◆ NROWS
| #define NROWS 5 |
Definition at line 122 of file cons_xor.c.
Referenced by addRelaxation(), allRowsInLP(), consdataCreate(), consdataFreeRows(), and separateCons().
Typedef Documentation
◆ Type
| typedef unsigned short Type |
type used for matrix entries in function checkGauss()
Definition at line 130 of file cons_xor.c.
◆ PROPRULE
Definition at line 179 of file cons_xor.c.
Enumeration Type Documentation
◆ Proprule
| enum Proprule |
Definition at line 171 of file cons_xor.c.
Function Documentation
◆ lockRounding()
|
static |
installs rounding locks for the given variable in the given xor constraint
- Parameters
-
scip SCIP data structure cons xor constraint var variable of constraint entry
Definition at line 188 of file cons_xor.c.
References SCIP_CALL, SCIP_LOCKTYPE_CONFLICT, SCIP_OKAY, SCIPconsIsLockedType(), SCIPlockVarCons(), TRUE, and unlockRounding().
Referenced by addCoef(), createRelaxation(), and setIntvar().
◆ unlockRounding()
|
static |
removes rounding locks for the given variable in the given xor constraint
- Parameters
-
scip SCIP data structure cons xor constraint var variable of constraint entry
Definition at line 204 of file cons_xor.c.
References conshdlrdataCreate(), SCIP_CALL, SCIP_LOCKTYPE_CONFLICT, SCIP_OKAY, SCIPconsIsLockedType(), SCIPunlockVarCons(), and TRUE.
Referenced by delCoefPos(), lockRounding(), and setIntvar().
◆ conshdlrdataCreate()
|
static |
creates constraint handler data
- Parameters
-
scip SCIP data structure conshdlrdata pointer to store the constraint handler data eventhdlr event handler
Definition at line 220 of file cons_xor.c.
References conshdlrdataFree(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.
Referenced by SCIPincludeConshdlrXor(), and unlockRounding().
◆ conshdlrdataFree()
|
static |
frees constraint handler data
- Parameters
-
scip SCIP data structure conshdlrdata pointer to the constraint handler data
Definition at line 240 of file cons_xor.c.
References consdataSwitchWatchedvars(), NULL, and SCIPfreeBlockMemory.
Referenced by conshdlrdataCreate(), and SCIP_DECL_CONSFREE().
◆ consdataSwitchWatchedvars()
|
static |
stores the given variable numbers as watched variables, and updates the event processing
- Parameters
-
scip SCIP data structure consdata xor constraint data eventhdlr event handler to call for the event processing watchedvar1 new first watched variable watchedvar2 new second watched variable
Definition at line 253 of file cons_xor.c.
References consdataEnsureVarsSize(), NULL, SCIP_CALL, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_OKAY, SCIPcatchVarEvent(), and SCIPdropVarEvent().
Referenced by consdataFree(), conshdlrdataFree(), delCoefPos(), and propagateCons().
◆ consdataEnsureVarsSize()
|
static |
ensures, that the vars array can store at least num entries
- Parameters
-
scip SCIP data structure consdata linear constraint data num minimum number of entries to store
Definition at line 317 of file cons_xor.c.
References consdataCreate(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.
Referenced by addCoef(), and consdataSwitchWatchedvars().
◆ consdataCreate()
|
static |
creates constraint data for xor constraint
- Parameters
-
scip SCIP data structure consdata pointer to store the constraint data rhs right hand side of the constraint nvars number of variables in the xor operation vars variables in xor operation intvar artificial integer variable for linear relaxation
Definition at line 341 of file cons_xor.c.
References consdataFreeRows(), CONSHDLR_NAME, FALSE, NROWS, NULL, r, SCIP_CALL, SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIPallocBlockMemory, SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPconshdlrGetData(), SCIPduplicateBlockMemoryArray, SCIPfindConshdlr(), SCIPgetStage(), SCIPgetTransformedVar(), SCIPgetTransformedVars(), SCIPisTransformed(), and TRUE.
Referenced by consdataEnsureVarsSize(), createConsXorIntvar(), SCIP_DECL_CONSTRANS(), and SCIPcreateConsXor().
◆ consdataFreeRows()
|
static |
releases LP row of constraint data
- Parameters
-
scip SCIP data structure consdata constraint data
Definition at line 416 of file cons_xor.c.
References consdataFree(), NROWS, NULL, r, SCIP_CALL, SCIP_OKAY, and SCIPreleaseRow().
Referenced by consdataCreate(), consdataFree(), and SCIP_DECL_CONSEXITSOL().
◆ consdataFree()
|
static |
frees constraint data for xor constraint
- Parameters
-
scip SCIP data structure consdata pointer to the constraint data eventhdlr event handler to call for the event processing
Definition at line 438 of file cons_xor.c.
References consdataFreeRows(), consdataPrint(), consdataSwitchWatchedvars(), NULL, SCIP_CALL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, SCIPisEQ(), SCIPisTransformed(), SCIPreleaseVar(), and SCIPvarGetLbGlobal().
Referenced by consdataFreeRows(), and SCIP_DECL_CONSDELETE().
◆ consdataPrint()
|
static |
prints xor constraint to file stream
- Parameters
-
scip SCIP data structure consdata xor constraint data file output file (or NULL for standard output) endline should an endline be set?
Definition at line 499 of file cons_xor.c.
References NULL, SCIP_CALL, SCIP_OKAY, SCIPinfoMessage(), SCIPwriteVarName(), SCIPwriteVarsList(), setIntvar(), and TRUE.
Referenced by applyFixings(), consdataFree(), and SCIP_DECL_CONSPRINT().
◆ setIntvar()
|
static |
sets intvar of an xor constraint
- Parameters
-
scip SCIP data structure cons xor constraint var variable to add to the constraint
Definition at line 533 of file cons_xor.c.
References addCoef(), lockRounding(), NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDCALL, SCIP_OKAY, SCIPcaptureVar(), SCIPconsGetData(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPgetTransformedVar(), SCIPreleaseVar(), SCIPvarIsTransformed(), TRUE, and unlockRounding().
Referenced by applyFixings(), consdataPrint(), and preprocessConstraintPairs().
◆ addCoef()
|
static |
adds coefficient to xor constraint
- Parameters
-
scip SCIP data structure cons xor constraint var variable to add to the constraint
Definition at line 585 of file cons_xor.c.
References consdataEnsureVarsSize(), CONSHDLR_NAME, delCoefPos(), lockRounding(), NULL, SCIP_Bool, SCIP_CALL, SCIP_EVENTTYPE_VARFIXED, SCIP_INVALIDCALL, SCIP_OKAY, SCIP_STAGE_EXITPRESOLVE, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_PRESOLVING, SCIPcatchVarEvent(), SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconsIsTransformed(), SCIPerrorMessage, SCIPfindConshdlr(), SCIPgetStage(), SCIPgetTransformedVar(), SCIPvarIsTransformed(), and TRUE.
Referenced by applyFixings(), preprocessConstraintPairs(), and setIntvar().
◆ delCoefPos()
|
static |
deletes coefficient at given position from xor constraint data
- Parameters
-
scip SCIP data structure cons xor constraint eventhdlr event handler to call for the event processing pos position of coefficient to delete
Definition at line 651 of file cons_xor.c.
References consdataSort(), consdataSwitchWatchedvars(), FALSE, NULL, SCIP_CALL, SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIP_STAGE_EXITPRESOLVE, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_PRESOLVING, SCIPconsGetData(), SCIPconsIsTransformed(), SCIPdropVarEvent(), SCIPgetStage(), SCIPvarIsTransformed(), TRUE, and unlockRounding().
Referenced by addCoef(), and applyFixings().
◆ consdataSort()
|
static |
sorts and constraint's variables by non-decreasing variable index
- Parameters
-
consdata constraint data
Definition at line 712 of file cons_xor.c.
References NULL, SCIP_DECL_HASHGETKEY(), SCIPsortPtr(), SCIPvarCompareActiveAndNegated(), and TRUE.
Referenced by applyFixings(), delCoefPos(), detectRedundantConstraints(), preprocessConstraintPairs(), and SCIP_DECL_HASHKEYEQ().
◆ SCIP_DECL_HASHGETKEY()
|
static |
gets the key of the given element
Definition at line 796 of file cons_xor.c.
References SCIP_DECL_HASHKEYEQ().
Referenced by consdataSort().
◆ SCIP_DECL_HASHKEYEQ()
|
static |
returns TRUE iff both keys are equal; two constraints are equal if they have the same variables
Definition at line 804 of file cons_xor.c.
References consdataSort(), FALSE, NULL, SCIP_DECL_HASHKEYVAL(), SCIPconsGetData(), SCIPvarCompare(), SCIPvarCompareActiveAndNegated(), and TRUE.
Referenced by SCIP_DECL_HASHGETKEY().
◆ SCIP_DECL_HASHKEYVAL()
|
static |
returns the hash value of the key
Definition at line 846 of file cons_xor.c.
References applyFixings(), NULL, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_NEGATED, SCIPconsGetData(), SCIPhashFour, SCIPvarGetIndex(), SCIPvarGetStatus(), and SCIPvarIsActive().
Referenced by SCIP_DECL_HASHKEYEQ().
◆ applyFixings()
|
static |
deletes all fixed variables and all pairs of equal variables
- Parameters
-
scip SCIP data structure cons xor constraint eventhdlr event handler to call for the event processing nchgcoefs pointer to add up the number of changed coefficients naggrvars pointer to add up the number of aggregated variables naddconss pointer to add up the number of added constraints cutoff whether a cutoff has been detected
Definition at line 878 of file cons_xor.c.
References addCoef(), addExtendedFlowFormulation(), consdataPrint(), consdataSort(), delCoefPos(), MAX, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_FIXED, SCIP_VARTYPE_BINARY, SCIPaddCons(), SCIPaddVar(), SCIPaggregateVars(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsDynamic(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsLinear(), SCIPcreateVar(), SCIPdebug, SCIPdebugMsg, SCIPdoNotAggr(), SCIPgetBinvarRepresentative(), SCIPisEQ(), SCIPreleaseCons(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNegationVar(), SCIPvarGetProbvar(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPvarIsInitial(), SCIPvarIsNegated(), SCIPvarIsRemovable(), setIntvar(), and TRUE.
Referenced by detectRedundantConstraints(), preprocessConstraintPairs(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_HASHKEYVAL().
◆ addExtendedFlowFormulation()
|
static |
adds extended flow formulation
The extended flow formulation is built as follows: Let \(x_1, \dots, x_k\) be the variables contained in the given XOR constraint. We construct a two layered flow network. The upper layer is called the north layer and the lower is called the south layer. For each \(x_i,\; i = 2, \ldots, k-1\), we add arcs that stay in the north and south layer (denoted by 'nn' and 'ss', respectively), as well as arcs that change the layers (denoted by 'ns' and 'sn'). For \(x_1\), we only add two arcs from the source to the two layers. The source is located on the north layer. For \(x_k\), we add two arcs connecting the two layers to the sink. Depending on the rhs of the constraint the sink is located on the north or south layer. A change in the layers corresponds to a parity change, i.e., the corresponding variable \(x_i\) is 1 (and 0 otherwise).
- Parameters
-
scip SCIP data structure cons constraint to check naggrvars pointer to add up the number of aggregated variables naddedconss number of added constraints
Definition at line 1151 of file cons_xor.c.
References addExtendedAsymmetricFormulation(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_IMPLINT, SCIPaddCons(), SCIPaddVar(), SCIPaggregateVars(), SCIPallocBlockMemoryArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPcreateConsLinear(), SCIPcreateVar(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPlockVarCons(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarIsTransformed(), and TRUE.
Referenced by applyFixings(), and SCIP_DECL_CONSPRESOL().
◆ addExtendedAsymmetricFormulation()
|
static |
adds extended asymmetric formulation
The extended asymmetric formulation is constructed as follows: Let \(x_1, \dots, x_k\) be the variables contained in the given XOR constraint. We introduce variables \(p_1, \ldots, p_k\) with the following constraints: \(p_1 = x_1\), \(p_k = 1\), and for \(i = 2, \ldots, k-1\):
\[ \begin{array}{ll} p_i & \leq p_{i-1} + x_i\\ p_i & \leq 2 - (p_{i-1} + x_i)\\ p_i & \geq p_{i-1} - x_i\\ p_i & \geq x_i - p_{i-1}. \end{array} \]
This formulation is described in
Robert D. Carr and Goran Konjevod
Polyhedral combinatorics
In Harvey Greenberg, editor, Tutorials on emerging methodologies and applications in Operations Research,
Chapter 2, pages (2-1)-(2-48). Springer, 2004.
- Parameters
-
scip SCIP data structure cons constraint to check naggrvars pointer to add up the number of aggregated variables naddedconss number of added constraints
Definition at line 1460 of file cons_xor.c.
References createRelaxation(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_IMPLINT, SCIPaddCons(), SCIPaddVar(), SCIPaggregateVars(), SCIPallocBlockMemoryArray, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsInitial(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPcreateConsLinear(), SCIPcreateVar(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPinfinity(), SCIPlockVarCons(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarIsTransformed(), and TRUE.
Referenced by addExtendedFlowFormulation(), and SCIP_DECL_CONSPRESOL().
◆ createRelaxation()
|
static |
creates LP row corresponding to xor constraint: x1 + ... + xn - 2q == rhs with internal integer variable q; in the special case of 3 variables and c = 0, the following linear system is created:
- x - y - z <= 0
- x + y - z <= 0
- x - y + z <= 0
- x + y + z <= 2 in the special case of 3 variables and c = 1, the following linear system is created:
- x + y + z <= 1
- x - y + z <= 1
- x + y - z <= 1
- x - y - z <= -1
- Parameters
-
scip SCIP data structure cons constraint to check
Definition at line 1641 of file cons_xor.c.
References addRelaxation(), lockRounding(), NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPaddVar(), SCIPaddVarsToRowSameCoef(), SCIPaddVarToRow(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPcreateVar(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPinfinity(), and SCIPsnprintf().
Referenced by addExtendedAsymmetricFormulation(), addRelaxation(), and separateCons().
◆ addRelaxation()
|
static |
adds linear relaxation of or constraint to the LP
- Parameters
-
scip SCIP data structure cons constraint to check infeasible pointer to store whether infeasibility was detected
Definition at line 1774 of file cons_xor.c.
References allRowsInLP(), createRelaxation(), FALSE, NROWS, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPaddRow(), SCIPconsGetData(), and SCIProwIsInLP().
Referenced by createRelaxation(), and SCIP_DECL_CONSINITLP().
◆ allRowsInLP()
|
static |
returns whether all rows of the LP relaxation are in the current LP
- Parameters
-
consdata constraint data
Definition at line 1806 of file cons_xor.c.
References checkCons(), FALSE, NROWS, NULL, r, SCIProwIsInLP(), and TRUE.
Referenced by addRelaxation(), and checkCons().
◆ checkCons()
|
static |
checks xor constraint for feasibility of given solution: returns TRUE iff constraint is feasible
- Parameters
-
scip SCIP data structure cons constraint to check sol solution to check, NULL for current solution checklprows Do constraints represented by rows in the current LP have to be checked? violated pointer to store whether the constraint is violated
Definition at line 1828 of file cons_xor.c.
References allRowsInLP(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPconsGetData(), SCIPgetSolVal(), SCIPincConsAge(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPresetConsAge(), SCIPupdateSolConsViolation(), separateCons(), and TRUE.
Referenced by allRowsInLP(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().
◆ separateCons()
|
static |
separates current LP solution
Consider a XOR-constraint
\[ x_1 \oplus x_2 \oplus \dots \oplus x_n = b \]
with \(b \in \{0,1\}\) and a solution \(x^*\) to be cut off. Small XOR constraints are handled by adding the inequalities of the convex hull.
The separation of larger XOR constraints has been described by
Xiaojie Zhang and Paul H. Siegel
"Adaptive Cut Generation Algorithm for Improved Linear Programming Decoding of Binary Linear Codes"
IEEE Transactions on Information Theory, vol. 58, no. 10, 2012
We separate the inequalities
\[ \sum_{j \in S} (1 - x_j) + \sum_{j \notin S} x_j \geq 1 \]
with \(|S| \equiv (b+1) \mbox{ mod } 2\) as follows. That these inequalities are valid can be seen as follows: Let \(x\) be a feasible solution and suppose that the inequality is violated for some \(S\). Then \(x_j = 1\) for all \(j \in S\) and \(x_j = 0\) for all \(j \notin S\). Thus we should have
\[ \oplus_{j \in S} x_j = |S| \mbox{ mod } 2 = b+1 \mbox{ mod } 2, \]
which is not equal to \(b\) as required by the XOR-constraint.
Let \(L= \{j \;:\; x^*_j > \frac{1}{2}\}\). Suppose that \(|L|\) has not the same parity as \(b\) rhs. Then
\[ \sum_{j \in L} (1 - x_j) + \sum_{j \notin L} x_j \geq 1 \]
is the only inequality that can be violated. We rewrite the inequality as
\[ \sum_{j \in L} x_j - \sum_{j \notin L} x_j \leq |L| - 1. \]
These inequalities are added.
Otherwise let \(k = \mbox{argmin}\{x^*_j \;:\; j \in L\}\) and check the inequality for \(L \setminus \{k\}\) and similarly for \(k = \mbox{argmax}\{x^*_j \;:\; j \in L\}\).
- Parameters
-
scip SCIP data structure cons constraint to check sol primal CIP solution, NULL for current LP solution separateparity should parity inequalities be separated? separated pointer to store whether a cut was found cutoff whether a cutoff has been detected
Definition at line 1943 of file cons_xor.c.
References computeRowEchelonGF2(), createRelaxation(), FALSE, NROWS, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPcreateEmptyRowCons(), SCIPdebug, SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetRowLPActivity(), SCIPgetRowSolFeasibility(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEfficacious(), SCIPisFeasGT(), SCIPisFeasNegative(), SCIPisGT(), SCIPprintRow(), SCIPreleaseRow(), SCIProwIsInLP(), SCIPsnprintf(), and TRUE.
Referenced by checkCons(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFORELAX(), SCIP_DECL_CONSSEPALP(), and SCIP_DECL_CONSSEPASOL().
◆ computeRowEchelonGF2()
|
static |
Transform linear system \(A x = b\) into row echelon form via the Gauss algorithm with row pivoting over GF2
- Returns
- the rank of
A
Here, \(A \in R^{m \times n},\; b \in R^m\). On exit, the vector p contains a permutation of the row indices used for pivoting and the function returns the rank r of A. For each row \(i = 1, \ldots, r\), the entry s[i] contains the column index of the first nonzero in row i.
- Parameters
-
scip SCIP data structure m number of rows n number of columns p row permutation s steps indicators of the row echelon form A matrix b rhs
Definition at line 2156 of file cons_xor.c.
References b, h, NULL, SCIPisStopped(), and solveRowEchelonGF2().
Referenced by checkSystemGF2(), and separateCons().
◆ solveRowEchelonGF2()
|
static |
Construct solution from matrix in row echelon form over GF2
Compute solution of \(A x = b\), which is already in row echelon form (
- See also
- computeRowEchelonGF2())
- Parameters
-
m number of rows n number of columns r rank of matrix p row permutation s steps indicators of the row echelon form A matrix b rhs x solution vector on exit
Definition at line 2265 of file cons_xor.c.
References b, checkSystemGF2(), NULL, r, and x.
Referenced by checkSystemGF2(), and computeRowEchelonGF2().
◆ checkSystemGF2()
|
static |
solve equation system over GF 2 by Gauss algorithm and create solution out of it or return cutoff
Collect all information in xor constraints into a linear system over GF2. Then solve the system by computing a row echelon form. If the system is infeasible, the current node is infeasible. Otherwise, we can compute a solution for the xor constraints given. We check whether this gives a solution for the whole problem.
We sort the columns with respect to the product of the objective coefficients and 1 minus the current LP solution value. The idea is that columns that are likely to provide the steps in the row echelon form should appear towards the front of the matrix. The smaller the product, the more it makes sense to set the variable to 1 (because the solution value is already close to 1 and the objective function is small).
Note that this function is called from propagation where usually no solution is available. However, the solution is only used for sorting the columns. Thus, the procedure stays correct even with nonsense solutions.
- Parameters
-
scip SCIP data structure conss xor constraints nconss number of xor constraints currentsol current solution (maybe NULL) result result of propagation (possibly cutoff, no change if primal solution has been tried)
Definition at line 2326 of file cons_xor.c.
References addConflictBounds(), b, BMSclearMemoryArray, computeRowEchelonGF2(), FALSE, MAXXORCONSSSYSTEM, MAXXORVARSSYSTEM, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIPallocBufferArray, SCIPblkmem(), SCIPcheckSol(), SCIPcomputeVarLbLocal(), SCIPcomputeVarUbLocal(), SCIPconsGetData(), SCIPconsGetName(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImageInt(), SCIPhashmapInsertInt(), SCIPheurPassSolAddSol(), SCIPinfoMessage(), SCIPisEQ(), SCIPisGE(), SCIPisLE(), SCIPisStopped(), SCIPprintSol(), SCIPsetSolVal(), SCIPsortRealIntPtr(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPvarIsNegated(), solveRowEchelonGF2(), TRUE, and x.
Referenced by SCIP_DECL_CONSPROP(), and solveRowEchelonGF2().
◆ addConflictBounds()
|
static |
for each variable in the xor constraint, add it to conflict set; for integral variable add corresponding bound
- Parameters
-
scip SCIP data structure cons constraint that inferred the bound change infervar variable that was deduced, or NULL (not equal to integral variable) bdchgidx bound change index (time stamp of bound change), or NULL for current time proprule propagation rule
Definition at line 2809 of file cons_xor.c.
References analyzeConflict(), FALSE, NULL, PROPRULE_0, PROPRULE_1, PROPRULE_INTLB, PROPRULE_INTUB, PROPRULE_INVALID, SCIP_CALL, SCIP_INVALIDDATA, SCIP_OKAY, SCIPABORT, SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPconsGetData(), SCIPconsGetName(), SCIPerrorMessage, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisEQ(), and TRUE.
Referenced by analyzeConflict(), checkSystemGF2(), and resolvePropagation().
◆ analyzeConflict()
|
static |
analyzes conflicting assignment on given constraint, and adds conflict constraint to problem
- Parameters
-
scip SCIP data structure cons xor constraint that detected the conflict infervar variable that was deduced, or NULL (not equal to integral variable) proprule propagation rule
Definition at line 2917 of file cons_xor.c.
References addConflictBounds(), FALSE, NULL, propagateCons(), SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_OKAY, SCIP_STAGE_SOLVING, SCIPanalyzeConflictCons(), SCIPgetStage(), SCIPinitConflictAnalysis(), SCIPinProbing(), and SCIPisConflictAnalysisApplicable().
Referenced by addConflictBounds(), and propagateCons().
◆ propagateCons()
|
static |
propagates constraint with the following rules: (0) all variables are fixed => can fix integral variable (1) all except one variable fixed => fix remaining variable and integral variable (2) depending on the amount of fixed binary variables we can tighten the integral variable (3) depending on the lower bound of the integral variable one can fix variables to 1 (4) depending on the upper bound of the integral variable one can fix variables to 0
- Parameters
-
scip SCIP data structure cons xor constraint to be processed eventhdlr event handler to call for the event processing cutoff pointer to store TRUE, if the node can be cut off nfixedvars pointer to add up the number of fixed variables nchgbds pointer to add up the number of found domain reductions
Definition at line 2948 of file cons_xor.c.
References analyzeConflict(), consdataSwitchWatchedvars(), FALSE, NULL, PROPRULE_0, PROPRULE_1, PROPRULE_INTLB, PROPRULE_INTUB, resolvePropagation(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_MULTAGGR, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPincConsAge(), SCIPinferBinvarCons(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinRepropagation(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), and TRUE.
Referenced by analyzeConflict(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().
◆ resolvePropagation()
|
static |
resolves a conflict on the given variable by supplying the variables needed for applying the corresponding propagation rules (see propagateCons())
- Parameters
-
scip SCIP data structure cons constraint that inferred the bound change infervar variable that was deduced proprule propagation rule that deduced the value bdchgidx bound change index (time stamp of bound change), or NULL for current time result pointer to store the result of the propagation conflict resolving call
Definition at line 3369 of file cons_xor.c.
References addConflictBounds(), cliquePresolve(), NULL, SCIP_CALL, SCIP_OKAY, SCIP_SUCCESS, and SCIPdebugMsg.
Referenced by propagateCons(), and SCIP_DECL_CONSRESPROP().
◆ cliquePresolve()
|
static |
try to use clique information to delete a part of the xor constraint or even fix variables
- Parameters
-
scip SCIP data structure cons constraint that inferred the bound change nfixedvars pointer to add up the number of found domain reductions nchgcoefs pointer to add up the number of deleted entries ndelconss pointer to add up the number of deleted constraints naddconss pointer to add up the number of added constraints cutoff pointer to store TRUE, if the node can be cut off
Definition at line 3390 of file cons_xor.c.
References detectRedundantConstraints(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_NEGATED, SCIPaddCoefSetppc(), SCIPaddCons(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsSetpart(), SCIPdebug, SCIPdebugMsg, SCIPdelCons(), SCIPfixVar(), SCIPgetNegatedVar(), SCIPprintCons(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetName(), SCIPvarGetNegationVar(), SCIPvarGetStatus(), SCIPvarIsActive(), SCIPvarsHaveCommonClique(), and TRUE.
Referenced by resolvePropagation(), and SCIP_DECL_CONSPRESOL().
◆ detectRedundantConstraints()
|
static |
compares each constraint with all other constraints for possible redundancy and removes or changes constraint accordingly; in contrast to preprocessConstraintPairs(), it uses a hash table
- Parameters
-
scip SCIP data structure blkmem block memory conss constraint set nconss number of constraints in constraint set firstchange pointer to store first changed constraint nchgcoefs pointer to add up the number of changed coefficients nfixedvars pointer to add up the number of found domain reductions naggrvars pointer to add up the number of aggregated variables ndelconss pointer to count number of deleted constraints naddconss pointer to count number of added constraints cutoff pointer to store TRUE, if a cutoff was found
Definition at line 3683 of file cons_xor.c.
References applyFixings(), consdataSort(), HASHSIZE_XORCONS, MAX, NULL, preprocessConstraintPairs(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaggregateVars(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetPos(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdelCons(), SCIPfixVar(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPswapPointers(), SCIPupdateConsFlags(), and TRUE.
Referenced by cliquePresolve(), and SCIP_DECL_CONSPRESOL().
◆ preprocessConstraintPairs()
|
static |
compares constraint with all prior constraints for possible redundancy or aggregation, and removes or changes constraint accordingly
- Parameters
-
scip SCIP data structure conss constraint set firstchange first constraint that changed since last pair preprocessing round chkind index of constraint to check against all prior indices upto startind cutoff pointer to store TRUE, if a cutoff was found nfixedvars pointer to add up the number of found domain reductions naggrvars pointer to count number of aggregated variables ndelconss pointer to count number of deleted constraints naddconss pointer to count number of added constraints nchgcoefs pointer to add up the number of changed coefficients
Definition at line 3880 of file cons_xor.c.
References addCoef(), applyFixings(), consdataSort(), createConsXorIntvar(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_INVALIDDATA, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPaddCons(), SCIPaggregateVars(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsDynamic(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelCons(), SCIPdoNotAggr(), SCIPerrorMessage, SCIPfixVar(), SCIPisStopped(), SCIPreleaseCons(), SCIPsnprintf(), SCIPupdateConsFlags(), SCIPvarCompareActiveAndNegated(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetProbvar(), SCIPvarIsActive(), setIntvar(), and TRUE.
Referenced by detectRedundantConstraints(), and SCIP_DECL_CONSPRESOL().
◆ createConsXorIntvar()
|
static |
creates and captures a xor constraint x_0 xor ... xor x_{k-1} = rhs with a given artificial integer variable for the linear relaxation
- Note
- the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
- Parameters
-
scip SCIP data structure cons pointer to hold the created constraint name name of constraint rhs right hand side of the constraint nvars number of operator variables in the constraint vars array with operator variables of constraint intvar artificial integer variable for linear relaxation initial should the LP relaxation of constraint be in the initial LP? Usually set to TRUE. Set to FALSE for 'lazy constraints'. separate should the constraint be separated during LP processing? Usually set to TRUE. enforce should the constraint be enforced during node processing? TRUE for model constraints, FALSE for additional, redundant constraints. check should the constraint be checked for feasibility? TRUE for model constraints, FALSE for additional, redundant constraints. propagate should the constraint be propagated during node processing? Usually set to TRUE. local is constraint only valid locally? Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. modifiable is constraint modifiable (subject to column generation)? Usually set to FALSE. In column generation applications, set to TRUE if pricing adds coefficients to this constraint. dynamic is constraint subject to aging? Usually set to FALSE. Set to TRUE for own cuts which are separated as constraints. removable should the relaxation be removed from the LP due to aging or cleanup? Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. stickingatnode should the constraint always be kept at the node where it was added, even if it may be moved to a more global node? Usually set to FALSE. Set to TRUE to for constraints that represent node data.
Definition at line 4463 of file cons_xor.c.
References consdataCreate(), CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_LINCONSUPGD(), SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIPcreateCons(), SCIPerrorMessage, and SCIPfindConshdlr().
Referenced by preprocessConstraintPairs(), SCIP_DECL_CONSCOPY(), SCIP_DECL_CONSPARSE(), and SCIP_DECL_LINCONSUPGD().
◆ SCIP_DECL_LINCONSUPGD()
|
static |
tries to upgrade a linear constraint into an xor constraint
Assuming all variables are binary and have coefficients with an absolute value 1, except for an integer (or binary) variable \(z\) which has coefficient \(a \in \{-2,2\}\) with absolute value 2 and appears only in this constraint, we can transform:
\[ \begin{array}{ll} & -\sum_{i \in I} x_i + \sum_{j \in J} x_j + a \cdot z = r \\ \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j + a \cdot z = r + |I| \\ \Leftrightarrow & \sum_{i \in I} \bar{x}_i + \sum_{j \in J} x_j - 2 \cdot y = (r + |I|) \text{ mod } 2, \end{array} \]
where
\[ y = \begin{cases} \left\lfloor \frac{r + |I|}{2} \right\rfloor + z & \text{if }a = -2\\ \left\lfloor \frac{r + |I|}{2} \right\rfloor - z & \text{if }a = 2. \end{cases} \]
If \(a = -2\) and \(z \in [\ell_z, u_z]\), then \(y \in [\ell_y, u_y]\), where \(\ell_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor + \ell_z\) and \(u_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor + u_z\).
If \(a = 2\), then \(\ell_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor - u_z\) and \(u_y = \left\lfloor \frac{r + |I|}{2} \right\rfloor - \ell_z\).
Then consider the resulting XOR-constraint
\[ \bigoplus_{i \in I} \bar{x}_i \oplus \bigoplus_{j \in j} x_j = (r + |I|) \text{ mod } 2. \]
If \(\ell_y \leq 0\) and \(u_y \geq (|I| + |J|)/2\), then the XOR constraint is a reformulation of the above transformed constraint, otherwise it is a relaxation because the bounds on the \(y\)-variable may disallow too many (or too few) operators set to 1. Therefore, the XOR constraint handler verifies in this case that the linear equation holds, ie., that the \(y\)-variable has the correct value.
Definition at line 4558 of file cons_xor.c.
References createConsXorIntvar(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_LOCKTYPE_MODEL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_NEGATED, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_INTEGER, SCIPaddVar(), SCIPaggregateVars(), SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateVar(), SCIPdebug, SCIPdebugMsg, SCIPdebugPrintCons, SCIPfeasFloor(), SCIPfloor(), SCIPfreeBufferArray, SCIPgetNegatedVar(), SCIPisEQ(), SCIPisFeasIntegral(), SCIPisFeasLE(), SCIPisIntegral(), SCIPisZero(), SCIPprintVar(), SCIPreleaseVar(), SCIPsnprintf(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetStatus(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPvarIsInitial(), SCIPvarIsRemovable(), and TRUE.
Referenced by createConsXorIntvar().
◆ SCIP_DECL_CONSHDLRCOPY()
|
static |
copy method for constraint handler plugins (called when SCIP copies plugins)
Definition at line 4756 of file cons_xor.c.
References CONSHDLR_NAME, NULL, SCIP_CALL, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrXor(), and TRUE.
Referenced by SCIP_DECL_LINCONSUPGD().
◆ SCIP_DECL_CONSFREE()
|
static |
destructor of constraint handler to free constraint handler data (called when SCIP is exiting)
Definition at line 4772 of file cons_xor.c.
References conshdlrdataFree(), NULL, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrSetData().
Referenced by SCIP_DECL_CONSHDLRCOPY().
◆ SCIP_DECL_CONSEXITSOL()
|
static |
solving process deinitialization method of constraint handler (called before branch and bound process data is freed)
Definition at line 4789 of file cons_xor.c.
References consdataFreeRows(), SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, and SCIPconsGetData().
Referenced by SCIP_DECL_CONSFREE().
◆ SCIP_DECL_CONSDELETE()
|
static |
frees specific constraint data
Definition at line 4807 of file cons_xor.c.
References consdataFree(), NULL, SCIP_CALL, SCIP_DECL_CONSTRANS(), SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIP_STAGE_INITPRESOLVE, SCIP_STAGE_PRESOLVING, SCIPconshdlrGetData(), SCIPdropVarEvent(), and SCIPgetStage().
Referenced by SCIP_DECL_CONSEXITSOL().
◆ SCIP_DECL_CONSTRANS()
|
static |
transforms constraint data into data belonging to the transformed problem
Definition at line 4833 of file cons_xor.c.
References consdataCreate(), NULL, SCIP_CALL, SCIP_DECL_CONSINITLP(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), and SCIPcreateCons().
Referenced by SCIP_DECL_CONSDELETE().
◆ SCIP_DECL_CONSINITLP()
|
static |
LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)
Definition at line 4859 of file cons_xor.c.
References addRelaxation(), FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, and SCIPconsIsInitial().
Referenced by SCIP_DECL_CONSTRANS().
◆ SCIP_DECL_CONSSEPALP()
|
static |
separation method of constraint handler for LP solutions
Definition at line 4879 of file cons_xor.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSSEPASOL(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), and separateCons().
Referenced by SCIP_DECL_CONSINITLP().
◆ SCIP_DECL_CONSSEPASOL()
|
static |
separation method of constraint handler for arbitrary primal solutions
Definition at line 4910 of file cons_xor.c.
References NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOLP(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), and separateCons().
Referenced by SCIP_DECL_CONSSEPALP().
◆ SCIP_DECL_CONSENFOLP()
|
static |
constraint enforcing method of constraint handler for LP solutions
Definition at line 4941 of file cons_xor.c.
References checkCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), and separateCons().
Referenced by SCIP_DECL_CONSSEPASOL().
◆ SCIP_DECL_CONSENFORELAX()
|
static |
constraint enforcing method of constraint handler for relaxation solutions
Definition at line 4978 of file cons_xor.c.
References checkCons(), FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_OKAY, SCIP_SEPARATED, SCIPconshdlrGetData(), and separateCons().
Referenced by SCIP_DECL_CONSENFOLP().
◆ SCIP_DECL_CONSENFOPS()
|
static |
constraint enforcing method of constraint handler for pseudo solutions
Definition at line 5015 of file cons_xor.c.
References checkCons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, and TRUE.
Referenced by SCIP_DECL_CONSENFORELAX().
◆ SCIP_DECL_CONSCHECK()
|
static |
feasibility check method of constraint handler for integral solutions
Definition at line 5038 of file cons_xor.c.
References checkCons(), NULL, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPROP(), SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIPconsGetData(), SCIPgetSolVal(), SCIPinfoMessage(), and SCIPprintCons().
Referenced by SCIP_DECL_CONSENFOPS().
◆ SCIP_DECL_CONSPROP()
|
static |
domain propagation method of constraint handler
Definition at line 5088 of file cons_xor.c.
References checkSystemGF2(), FALSE, NULL, propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSINITPRE(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_REDUCEDDOM, SCIPconshdlrGetData(), SCIPgetDepth(), and SCIPinProbing().
Referenced by SCIP_DECL_CONSCHECK().
◆ SCIP_DECL_CONSINITPRE()
|
static |
presolving initialization method of constraint handler (called when presolving is about to begin)
Definition at line 5137 of file cons_xor.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSEXITPRE(), SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIPcatchVarEvent(), SCIPconsGetData(), and SCIPconshdlrGetData().
Referenced by SCIP_DECL_CONSPROP().
◆ SCIP_DECL_CONSEXITPRE()
|
static |
presolving deinitialization method of constraint handler (called after presolving has been finished)
Definition at line 5166 of file cons_xor.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSPRESOL(), SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconsIsDeleted(), and SCIPdropVarEvent().
Referenced by SCIP_DECL_CONSINITPRE().
◆ SCIP_DECL_CONSPRESOL()
|
static |
presolving method of constraint handler
Definition at line 5198 of file cons_xor.c.
References addExtendedAsymmetricFormulation(), addExtendedFlowFormulation(), applyFixings(), cliquePresolve(), detectRedundantConstraints(), FALSE, MINGAINPERNMINCOMPARISONS, NMINCOMPARISONS, NULL, preprocessConstraintPairs(), propagateCons(), SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSRESPROP(), SCIP_DIDNOTFIND, SCIP_Longint, SCIP_OKAY, SCIP_PRESOLTIMING_EXHAUSTIVE, SCIP_PRESOLTIMING_MEDIUM, SCIP_Real, SCIP_SUCCESS, SCIPaggregateVars(), SCIPblkmem(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsDeleted(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelCons(), SCIPdoNotAggr(), SCIPisEQ(), SCIPisPresolveFinished(), SCIPisStopped(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), and TRUE.
Referenced by SCIP_DECL_CONSEXITPRE().
◆ SCIP_DECL_CONSRESPROP()
|
static |
propagation conflict resolving method of constraint handler
Definition at line 5413 of file cons_xor.c.
References resolvePropagation(), SCIP_CALL, SCIP_DECL_CONSLOCK(), and SCIP_OKAY.
Referenced by SCIP_DECL_CONSPRESOL().
◆ SCIP_DECL_CONSLOCK()
|
static |
variable rounding lock method of constraint handler
Definition at line 5423 of file cons_xor.c.
References NULL, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_LOCKTYPE_MODEL, SCIP_OKAY, SCIPaddVarLocksType(), and SCIPconsGetData().
Referenced by SCIP_DECL_CONSRESPROP().
◆ SCIP_DECL_CONSPRINT()
|
static |
constraint display method of constraint handler
Definition at line 5451 of file cons_xor.c.
References consdataPrint(), FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSCOPY(), SCIP_OKAY, and SCIPconsGetData().
Referenced by SCIP_DECL_CONSLOCK().
◆ SCIP_DECL_CONSCOPY()
|
static |
constraint copying method of constraint handler
Definition at line 5464 of file cons_xor.c.
References createConsXorIntvar(), NULL, SCIP_CALL, SCIP_DECL_CONSPARSE(), SCIP_OKAY, SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetRhsXor(), SCIPgetVarCopy(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.
Referenced by SCIP_DECL_CONSPRINT().
◆ SCIP_DECL_CONSPARSE()
|
static |
constraint parsing method of constraint handler
Definition at line 5558 of file cons_xor.c.
References createConsXorIntvar(), FALSE, NULL, SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcreateConsXor(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPerrorMessage, SCIPfreeBufferArray, SCIPisEQ(), SCIPisZero(), SCIPparseReal(), SCIPparseVarName(), SCIPparseVarsList(), SCIPreallocBufferArray, SCIPskipSpace(), and TRUE.
Referenced by SCIP_DECL_CONSCOPY().
◆ SCIP_DECL_CONSGETVARS()
|
static |
constraint method of constraint handler which returns the variables (if possible)
Definition at line 5687 of file cons_xor.c.
References BMScopyMemoryArray, FALSE, NULL, SCIP_DECL_CONSGETNVARS(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
Referenced by SCIP_DECL_CONSPARSE().
◆ SCIP_DECL_CONSGETNVARS()
|
static |
constraint method of constraint handler which returns the number of variable (if possible)
Definition at line 5729 of file cons_xor.c.
References NULL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPconsGetData(), and TRUE.
Referenced by SCIP_DECL_CONSGETVARS().
◆ SCIP_DECL_EVENTEXEC()
|
static |
Definition at line 5753 of file cons_xor.c.
References FALSE, NULL, SCIP_EVENTTYPE_VARFIXED, SCIP_OKAY, SCIP_STAGE_PRESOLVING, SCIPeventGetType(), SCIPeventGetVar(), SCIPgetStage(), and SCIPincludeConshdlrXor().
Referenced by SCIP_DECL_CONSGETNVARS().