Detailed Description

Constraint handler for "xor" constraints, \(rhs = x_1 \oplus x_2 \oplus \dots \oplus x_n\).

Author: Tobias Achterberg; Stefan Heinz; Marc Pfetsch; Michael Winkler

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"
#include <string.h>

Go to the source code of this file.

Macros
#define	CONSHDLR_NAME "xor"

#define	CONSHDLR_DESC "constraint handler for xor constraints: r = xor(x1, ..., xn)"

#define	CONSHDLR_SEPAPRIORITY +850200

#define	CONSHDLR_ENFOPRIORITY -850200

#define	CONSHDLR_CHECKPRIORITY -850200

#define	CONSHDLR_SEPAFREQ 0

#define	CONSHDLR_PROPFREQ 1

#define	CONSHDLR_EAGERFREQ 100

#define	CONSHDLR_MAXPREROUNDS -1

#define	CONSHDLR_DELAYSEPA FALSE

#define	CONSHDLR_DELAYPROP FALSE

#define	CONSHDLR_NEEDSCONS TRUE

#define	CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

#define	CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

#define	EVENTHDLR_NAME "xor"

#define	EVENTHDLR_DESC "event handler for xor constraints"

#define	LINCONSUPGD_PRIORITY +600000

#define	DEFAULT_PRESOLPAIRWISE TRUE

#define	DEFAULT_ADDEXTENDEDFORM FALSE

#define	DEFAULT_ADDFLOWEXTENDED FALSE

#define	DEFAULT_SEPARATEPARITY FALSE

#define	DEFAULT_GAUSSPROPFREQ 5

#define	HASHSIZE_XORCONS 500

#define	DEFAULT_PRESOLUSEHASHING TRUE

#define	NMINCOMPARISONS 200000

#define	MINGAINPERNMINCOMPARISONS 1e-06

#define	MAXXORCONSSSYSTEM 1000

#define	MAXXORVARSSYSTEM 1000

#define	NROWS 5

Typedefs
typedef unsigned short	Type

typedef enum Proprule	PROPRULE

Enumerations
enum	Proprule { PROPRULE_1, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_INVALID, PROPRULE_INVALID = 0, PROPRULE_1 = 1, PROPRULE_2 = 2, PROPRULE_3 = 3, PROPRULE_4 = 4, 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, PROPRULE_2, PROPRULE_3, PROPRULE_4, PROPRULE_INVALID, 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 SCIP_RETCODE	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 *naddedconss)

static SCIP_RETCODE	addExtendedAsymmetricFormulation (SCIP scip, SCIP_CONS cons, 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	computeRowEcholonGF2 (SCIP scip, int m, int n, int p, int s, Type A, Type b)

static void	solveRowEcholonGF2 (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 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 69 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 70 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY +850200

priority of the constraint handler for separation

Definition at line 71 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 72 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 73 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 74 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 75 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 76 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 79 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 80 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 81 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 82 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP

Definition at line 84 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_ALWAYS

Definition at line 85 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ EVENTHDLR_NAME

#define EVENTHDLR_NAME "xor"

Definition at line 87 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ EVENTHDLR_DESC

#define EVENTHDLR_DESC "event handler for xor constraints"

Definition at line 88 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 90 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 92 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 93 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 94 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ DEFAULT_SEPARATEPARITY

#define DEFAULT_SEPARATEPARITY FALSE

should parity inequalities be separated?

Definition at line 95 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ DEFAULT_GAUSSPROPFREQ

#define DEFAULT_GAUSSPROPFREQ 5

frequency for applying the Gauss propagator

Definition at line 96 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 97 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 98 of file cons_xor.c.

Referenced by SCIPincludeConshdlrXor().

◆ NMINCOMPARISONS

#define NMINCOMPARISONS 200000

number for minimal pairwise presolving comparisons

Definition at line 99 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 100 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 101 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 102 of file cons_xor.c.

Referenced by checkSystemGF2().

◆ NROWS

#define NROWS 5

Definition at line 104 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 112 of file cons_xor.c.

◆ PROPRULE

typedef enum Proprule PROPRULE

Definition at line 161 of file cons_xor.c.

Enumeration Type Documentation

◆ Proprule

enum Proprule

Enumerator
PROPRULE_1	left hand side and bounds on z -> lower bound on x
PROPRULE_2	left hand side and upper bound on x -> bound on z
PROPRULE_3	right hand side and bounds on z -> upper bound on x
PROPRULE_4	right hand side and lower bound on x -> bound on z
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_1	v_i = FALSE => r = FALSE
PROPRULE_2	r = TRUE => v_i = TRUE for all i
PROPRULE_3	v_i = TRUE for all i => r = TRUE
PROPRULE_4	r = FALSE, v_i = TRUE for all i except j => v_j = FALSE
PROPRULE_1_CORETIMES	core-time propagator
PROPRULE_2_EDGEFINDING	edge-finder
PROPRULE_3_TTEF	time-table edeg-finding
PROPRULE_1_RHS	activity residuals of all other variables tighten bounds of single variable due to the right hand side of the inequality
PROPRULE_1_LHS	activity residuals of all other variables tighten bounds of single variable due to the left hand side of the inequality
PROPRULE_1_RANGEDROW	fixed variables and gcd of all left variables tighten bounds of a single variable in this reanged row
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_1	v_i = TRUE => r = TRUE
PROPRULE_2	r = FALSE => v_i = FALSE for all i
PROPRULE_3	v_i = FALSE for all i => r = FALSE
PROPRULE_4	r = TRUE, v_i = FALSE for all i except j => v_j = TRUE
PROPRULE_INVALID	propagation was applied without a specific propagation rule
PROPRULE_1	left hand side and bounds on y -> lower bound on x
PROPRULE_2	left hand side and upper bound on x -> bound on y
PROPRULE_3	right hand side and bounds on y -> upper bound on x
PROPRULE_4	right hand side and lower bound on x -> bound on y
PROPRULE_0	all variables are fixed => fix integral variable
PROPRULE_1	all except one variable fixed => fix remaining variable
PROPRULE_INTLB	lower bound propagation of integral variable
PROPRULE_INTUB	upper bound propagation of integral variable
PROPRULE_INVALID	propagation was applied without a specific propagation rule

Definition at line 153 of file cons_xor.c.

Function Documentation

◆ lockRounding()

static SCIP_RETCODE lockRounding	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

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 170 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 SCIP_RETCODE unlockRounding	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

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 186 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 SCIP_RETCODE conshdlrdataCreate	(	SCIP *	scip,
		SCIP_CONSHDLRDATA **	conshdlrdata,
		SCIP_EVENTHDLR *	eventhdlr
	)

static

creates constraint handler data

Parameters

scip	SCIP data structure
conshdlrdata	pointer to store the constraint handler data
eventhdlr	event handler

Definition at line 202 of file cons_xor.c.

References conshdlrdataFree(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory.

Referenced by SCIPincludeConshdlrXor(), and unlockRounding().

◆ conshdlrdataFree()

static SCIP_RETCODE conshdlrdataFree	(	SCIP *	scip,
		SCIP_CONSHDLRDATA **	conshdlrdata
	)

static

frees constraint handler data

Parameters

scip	SCIP data structure
conshdlrdata	pointer to the constraint handler data

Definition at line 222 of file cons_xor.c.

References consdataSwitchWatchedvars(), NULL, SCIP_OKAY, and SCIPfreeBlockMemory.

Referenced by conshdlrdataCreate(), and SCIP_DECL_CONSFREE().

◆ consdataSwitchWatchedvars()

static SCIP_RETCODE consdataSwitchWatchedvars	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		SCIP_EVENTHDLR *	eventhdlr,
		int	watchedvar1,
		int	watchedvar2
	)

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 237 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 SCIP_RETCODE consdataEnsureVarsSize	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		int	num
	)

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 301 of file cons_xor.c.

References consdataCreate(), NULL, SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), and SCIPreallocBlockMemoryArray.

Referenced by addCoef(), and consdataSwitchWatchedvars().

◆ consdataCreate()

static SCIP_RETCODE consdataCreate	(	SCIP *	scip,
		SCIP_CONSDATA **	consdata,
		SCIP_Bool	rhs,
		int	nvars,
		SCIP_VAR **	vars,
		SCIP_VAR *	intvar
	)

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 325 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 SCIP_RETCODE consdataFreeRows	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata
	)

static

releases LP row of constraint data

Parameters

scip	SCIP data structure
consdata	constraint data

Definition at line 400 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 SCIP_RETCODE consdataFree	(	SCIP *	scip,
		SCIP_CONSDATA **	consdata,
		SCIP_EVENTHDLR *	eventhdlr
	)

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 422 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 SCIP_RETCODE consdataPrint	(	SCIP *	scip,
		SCIP_CONSDATA *	consdata,
		FILE *	file,
		SCIP_Bool	endline
	)

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 483 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 SCIP_RETCODE setIntvar	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

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 517 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 SCIP_RETCODE addCoef	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	var
	)

static

adds coefficient to xor constraint

Parameters

scip	SCIP data structure
cons	xor constraint
var	variable to add to the constraint

Definition at line 569 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 SCIP_RETCODE delCoefPos	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_EVENTHDLR *	eventhdlr,
		int	pos
	)

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 635 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 void consdataSort ( SCIP_CONSDATA * consdata )

static

sorts and constraint's variables by non-decreasing variable index

Parameters

consdata constraint data

Definition at line 696 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 SCIP_DECL_HASHGETKEY ( hashGetKeyXorcons )

static

gets the key of the given element

Definition at line 780 of file cons_xor.c.

References SCIP_DECL_HASHKEYEQ().

Referenced by consdataSort().

◆ SCIP_DECL_HASHKEYEQ()

static SCIP_DECL_HASHKEYEQ ( hashKeyEqXorcons )

static

returns TRUE iff both keys are equal; two constraints are equal if they have the same variables

Definition at line 788 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 SCIP_DECL_HASHKEYVAL ( hashKeyValXorcons )

static

returns the hash value of the key

Definition at line 830 of file cons_xor.c.

References applyFixings(), NULL, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_NEGATED, SCIPcombineTwoInt, SCIPconsGetData(), SCIPhashTwo, SCIPvarGetIndex(), SCIPvarGetStatus(), and SCIPvarIsActive().

Referenced by SCIP_DECL_HASHKEYEQ().

◆ applyFixings()

static SCIP_RETCODE applyFixings	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_EVENTHDLR *	eventhdlr,
		int *	nchgcoefs,
		int *	naggrvars,
		int *	naddconss,
		SCIP_Bool *	cutoff
	)

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 863 of file cons_xor.c.

References addCoef(), addExtendedFlowFormulation(), consdataPrint(), consdataSort(), delCoefPos(), MIN, 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 SCIP_RETCODE addExtendedFlowFormulation	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	naddedconss
	)

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
naddedconss	number of added constraints

Definition at line 1133 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 SCIP_RETCODE addExtendedAsymmetricFormulation	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	naddedconss
	)

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
naddedconss	number of added constraints

Definition at line 1438 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 SCIP_RETCODE createRelaxation	(	SCIP *	scip,
		SCIP_CONS *	cons
	)

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 1617 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(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsRemovable(), SCIPcreateEmptyRowCons(), SCIPcreateVar(), SCIPdebugAddSolVal, SCIPdebugGetSolVal, SCIPinfinity(), and SCIPsnprintf().

Referenced by addExtendedAsymmetricFormulation(), addRelaxation(), and separateCons().

◆ addRelaxation()

static SCIP_RETCODE addRelaxation	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_Bool *	infeasible
	)

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 1750 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 SCIP_Bool allRowsInLP ( SCIP_CONSDATA * consdata )

static

returns whether all rows of the LP relaxation are in the current LP

Parameters

consdata constraint data

Definition at line 1782 of file cons_xor.c.

References checkCons(), FALSE, NROWS, NULL, r, SCIProwIsInLP(), and TRUE.

Referenced by addRelaxation(), and checkCons().

◆ checkCons()

static SCIP_RETCODE checkCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Bool	checklprows,
		SCIP_Bool *	violated
	)

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 1804 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 SCIP_RETCODE separateCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_SOL *	sol,
		SCIP_Bool	separateparity,
		SCIP_Bool *	separated,
		SCIP_Bool *	cutoff
	)

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 1919 of file cons_xor.c.

References computeRowEcholonGF2(), createRelaxation(), FALSE, NROWS, NULL, r, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), 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().

◆ computeRowEcholonGF2()

static int computeRowEcholonGF2	(	SCIP *	scip,
		int	m,
		int	n,
		int *	p,
		int *	s,
		Type **	A,
		Type *	b
	)

static

Transform linear system \(A x = b\) into row echolon 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 echolon form
A	matrix
b	rhs

Definition at line 2132 of file cons_xor.c.

References b, h, NULL, SCIPisStopped(), and solveRowEcholonGF2().

Referenced by checkSystemGF2(), and separateCons().

◆ solveRowEcholonGF2()

static void solveRowEcholonGF2	(	int	m,
		int	n,
		int	r,
		int *	p,
		int *	s,
		Type **	A,
		Type *	b,
		Type *	x
	)

static

Construct solution from matrix in row echolon form over GF2

Compute solution of \(A x = b\), which is already in row echolon form (

See also: computeRowEcholonGF2())

Parameters

m	number of rows
n	number of columns
r	rank of matrix
p	row permutation
s	steps indicators of the row echolon form
A	matrix
b	rhs
x	solution vector on exit

Definition at line 2241 of file cons_xor.c.

References b, checkSystemGF2(), NULL, r, and x.

Referenced by checkSystemGF2(), and computeRowEcholonGF2().

◆ checkSystemGF2()

static SCIP_RETCODE checkSystemGF2	(	SCIP *	scip,
		SCIP_CONS **	conss,
		int	nconss,
		SCIP_SOL *	currentsol,
		SCIP_RESULT *	result
	)

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 echolon 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 echolon 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 2305 of file cons_xor.c.

References addConflictBounds(), b, BMSclearMemoryArray, computeRowEcholonGF2(), FALSE, MAXXORCONSSSYSTEM, MAXXORVARSSYSTEM, NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_FIXED, SCIP_VARSTATUS_MULTAGGR, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPblkmem(), SCIPcheckSol(), SCIPcomputeVarLbLocal(), SCIPcomputeVarUbLocal(), SCIPconsGetData(), SCIPconsGetName(), SCIPcreateSol(), SCIPdebug, SCIPdebugMsg, SCIPfindHeur(), SCIPfreeBufferArray, SCIPfreeSol(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPhashmapCreate(), SCIPhashmapExists(), SCIPhashmapFree(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPheurPassSolAddSol(), SCIPinfoMessage(), SCIPisEQ(), SCIPisGE(), SCIPisLE(), SCIPisStopped(), SCIPprintSol(), SCIPsetSolVal(), SCIPsortRealIntPtr(), SCIPtightenVarLb(), SCIPtightenVarUb(), SCIPvarGetAggrConstant(), SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetNegatedVar(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPvarIsNegated(), solveRowEcholonGF2(), TRUE, and x.

Referenced by SCIP_DECL_CONSPROP(), and solveRowEcholonGF2().

◆ addConflictBounds()

static SCIP_RETCODE addConflictBounds	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	infervar,
		SCIP_BDCHGIDX *	bdchgidx,
		PROPRULE	proprule
	)

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 2784 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 SCIP_RETCODE analyzeConflict	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	infervar,
		PROPRULE	proprule
	)

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 2892 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 SCIP_RETCODE propagateCons	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_EVENTHDLR *	eventhdlr,
		SCIP_Bool *	cutoff,
		int *	nfixedvars,
		int *	nchgbds
	)

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 2923 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, SCIPconsGetData(), SCIPconsGetName(), SCIPconsIsModifiable(), SCIPdebugMsg, SCIPdelConsLocal(), SCIPincConsAge(), SCIPinferBinvarCons(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinRepropagation(), SCIPisEQ(), SCIPisFeasEQ(), SCIPisFeasIntegral(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetUbLocal(), and TRUE.

Referenced by analyzeConflict(), SCIP_DECL_CONSPRESOL(), and SCIP_DECL_CONSPROP().

◆ resolvePropagation()

static SCIP_RETCODE resolvePropagation	(	SCIP *	scip,
		SCIP_CONS *	cons,
		SCIP_VAR *	infervar,
		PROPRULE	proprule,
		SCIP_BDCHGIDX *	bdchgidx,
		SCIP_RESULT *	result
	)

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 3321 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 SCIP_RETCODE cliquePresolve	(	SCIP *	scip,
		SCIP_CONS *	cons,
		int *	nfixedvars,
		int *	nchgcoefs,
		int *	ndelconss,
		int *	naddconss,
		SCIP_Bool *	cutoff
	)

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 3342 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 SCIP_RETCODE detectRedundantConstraints	(	SCIP *	scip,
		BMS_BLKMEM *	blkmem,
		SCIP_CONS **	conss,
		int	nconss,
		int *	firstchange,
		int *	nchgcoefs,
		int *	naggrvars,
		int *	ndelconss,
		int *	naddconss,
		SCIP_Bool *	cutoff
	)

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
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 3635 of file cons_xor.c.

References applyFixings(), consdataSort(), HASHSIZE_XORCONS, MAX, NULL, preprocessConstraintPairs(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetPos(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPdelCons(), SCIPhashtableCreate(), SCIPhashtableFree(), SCIPhashtableInsert(), SCIPhashtableRetrieve(), SCIPupdateConsFlags(), and TRUE.

Referenced by cliquePresolve(), and SCIP_DECL_CONSPRESOL().

◆ preprocessConstraintPairs()

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

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 3752 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 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

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 4283 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 SCIP_DECL_LINCONSUPGD ( linconsUpgdXor )

static

tries to upgrade a linear constraint into an xor constraint

Assuming the only coefficients with an absolute value unequal to one is two in absolute value we can transform:

\[ \begin{array}{ll} & -\sum_{i \in I} x_i + \sum_{j \in J} x_j + a \cdot z = rhs \\ \Leftrightarrow & \sum_{i \in I} ~x_i + \sum_j x_{j \in J} + a \cdot z = rhs + |I| \\ \Leftrightarrow & \sum_{i \in I} ~x_i + \sum_j x_{j \in J} - 2 \cdot y = (rhs + |I|) mod 2 \\ & z \in [lb_z,ub_z] \Rightarrow y \in (\left\lfloor \frac{rhs + |I|}{2} \right\rfloor + (a = -2\; ?\; lb_z : -ub_z), \left\lfloor \frac{rhs + |I|}{2} \right\rfloor + (a = -2\; ?\; ub_z : -lb_z) ) \\ & z = (a = -2\; ?\; y - \left\lfloor \frac{rhs + |I|}{2} \right\rfloor\; :\; -y + \left\lfloor \frac{rhs + |I|}{2} \right\rfloor) \end{array} \]

Definition at line 4357 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_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(), SCIPvarGetNLocksDownType(), SCIPvarGetNLocksUpType(), SCIPvarGetUbGlobal(), SCIPvarIsActive(), SCIPvarIsBinary(), SCIPvarIsInitial(), and SCIPvarIsRemovable().

Referenced by createConsXorIntvar().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyXor )

static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 4542 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 SCIP_DECL_CONSFREE ( consFreeXor )

static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 4558 of file cons_xor.c.

References conshdlrdataFree(), NULL, SCIP_CALL, SCIP_DECL_CONSEXITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrSetData().

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolXor )

static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 4575 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 SCIP_DECL_CONSDELETE ( consDeleteXor )

static

frees specific constraint data

Definition at line 4593 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 SCIP_DECL_CONSTRANS ( consTransXor )

static

transforms constraint data into data belonging to the transformed problem

Definition at line 4619 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 SCIP_DECL_CONSINITLP ( consInitlpXor )

static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

Definition at line 4645 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 SCIP_DECL_CONSSEPALP ( consSepalpXor )

static

separation method of constraint handler for LP solutions

Definition at line 4665 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 SCIP_DECL_CONSSEPASOL ( consSepasolXor )

static

separation method of constraint handler for arbitrary primal solutions

Definition at line 4696 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 SCIP_DECL_CONSENFOLP ( consEnfolpXor )

static

constraint enforcing method of constraint handler for LP solutions

Definition at line 4727 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 SCIP_DECL_CONSENFORELAX ( consEnforelaxXor )

static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 4764 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 SCIP_DECL_CONSENFOPS ( consEnfopsXor )

static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 4801 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 SCIP_DECL_CONSCHECK ( consCheckXor )

static

feasibility check method of constraint handler for integral solutions

Definition at line 4824 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 SCIP_DECL_CONSPROP ( consPropXor )

static

domain propagation method of constraint handler

Definition at line 4874 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 SCIP_DECL_CONSINITPRE ( consInitpreXor )

static

presolving initialization method of constraint handler (called when presolving is about to begin)

Definition at line 4923 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 SCIP_DECL_CONSEXITPRE ( consExitpreXor )

static

presolving deinitialization method of constraint handler (called after presolving has been finished)

Definition at line 4952 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 SCIP_DECL_CONSPRESOL ( consPresolXor )

static

presolving method of constraint handler

Definition at line 4984 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 SCIP_DECL_CONSRESPROP ( consRespropXor )

static

propagation conflict resolving method of constraint handler

Definition at line 5198 of file cons_xor.c.

References resolvePropagation(), SCIP_CALL, SCIP_DECL_CONSLOCK(), and SCIP_OKAY.

Referenced by SCIP_DECL_CONSPRESOL().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockXor )

static

variable rounding lock method of constraint handler

Definition at line 5208 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 SCIP_DECL_CONSPRINT ( consPrintXor )

static

constraint display method of constraint handler

Definition at line 5236 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 SCIP_DECL_CONSCOPY ( consCopyXor )

static

constraint copying method of constraint handler

Definition at line 5249 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 SCIP_DECL_CONSPARSE ( consParseXor )

static

constraint parsing method of constraint handler

Definition at line 5340 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(), SCIPparseVarName(), SCIPparseVarsList(), SCIPreallocBufferArray, SCIPstrToRealValue(), SCIPvarGetName(), and TRUE.

Referenced by SCIP_DECL_CONSCOPY().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsXor )

static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 5472 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 SCIP_DECL_CONSGETNVARS ( consGetNVarsXor )

static

constraint method of constraint handler which returns the number of variable (if possible)

Definition at line 5514 of file cons_xor.c.

References NULL, SCIP_DECL_EVENTEXEC(), SCIP_OKAY, SCIPconsGetData(), and TRUE.

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecXor )

static

Definition at line 5538 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().

SCIP

Detailed Description

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

◆ CONSHDLR_SEPAPRIORITY

◆ CONSHDLR_ENFOPRIORITY

◆ CONSHDLR_CHECKPRIORITY

◆ CONSHDLR_SEPAFREQ

◆ CONSHDLR_PROPFREQ

◆ CONSHDLR_EAGERFREQ

◆ CONSHDLR_MAXPREROUNDS

◆ CONSHDLR_DELAYSEPA

◆ CONSHDLR_DELAYPROP

◆ CONSHDLR_NEEDSCONS

◆ CONSHDLR_PROP_TIMING

◆ CONSHDLR_PRESOLTIMING

◆ EVENTHDLR_NAME

◆ EVENTHDLR_DESC

◆ LINCONSUPGD_PRIORITY

◆ DEFAULT_PRESOLPAIRWISE

◆ DEFAULT_ADDEXTENDEDFORM

◆ DEFAULT_ADDFLOWEXTENDED

◆ DEFAULT_SEPARATEPARITY

◆ DEFAULT_GAUSSPROPFREQ

◆ HASHSIZE_XORCONS

◆ DEFAULT_PRESOLUSEHASHING

◆ NMINCOMPARISONS

◆ MINGAINPERNMINCOMPARISONS

◆ MAXXORCONSSSYSTEM

◆ MAXXORVARSSYSTEM

◆ NROWS

Typedef Documentation

◆ Type

◆ PROPRULE

Enumeration Type Documentation

◆ Proprule

Function Documentation

◆ lockRounding()

◆ unlockRounding()

◆ conshdlrdataCreate()

◆ conshdlrdataFree()

◆ consdataSwitchWatchedvars()

◆ consdataEnsureVarsSize()

◆ consdataCreate()

◆ consdataFreeRows()

◆ consdataFree()

◆ consdataPrint()

◆ setIntvar()

◆ addCoef()

◆ delCoefPos()

◆ consdataSort()

◆ SCIP_DECL_HASHGETKEY()

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ applyFixings()

◆ addExtendedFlowFormulation()

◆ addExtendedAsymmetricFormulation()

◆ createRelaxation()

◆ addRelaxation()

◆ allRowsInLP()

◆ checkCons()

◆ separateCons()

◆ computeRowEcholonGF2()

◆ solveRowEcholonGF2()

◆ checkSystemGF2()

◆ addConflictBounds()

◆ analyzeConflict()

◆ propagateCons()

◆ resolvePropagation()

◆ cliquePresolve()

◆ detectRedundantConstraints()

◆ preprocessConstraintPairs()

◆ createConsXorIntvar()

◆ SCIP_DECL_LINCONSUPGD()

◆ SCIP_DECL_CONSHDLRCOPY()