Parity Constraint¶

Definition¶

For three binary decisions $y_1,y_2,y_3$, requiring an even number of yes decisions is equivalent to

The sum can therefore be 0 or 2, the only even values possible for three binary decisions.

Interpretation¶

The parity constraint counts yes decisions and requires the count to be even. Three binary decisions sum to at most $3$, so the even counts are $0$ and $2$, and the auxiliary variable $x\in\{0,1\}$ in $y_1+y_2+y_3=2x$ produces exactly these.

The number line shows the four possible counts. The even ones are reached with $x=0$ (all three no) and $x=1$ (exactly two yes); the odd counts $1$ and $3$ would need $x=\tfrac{1}{2}$ or $x=\tfrac{3}{2}$$\frac{3}{2}$, which are not allowed.

The parity condition comes from $x$ being an integer. If $x$ is relaxed to a continuous variable with $0\le x\le1$$1$, the odd count $1$ becomes feasible with $x=1/2$$1/2$, so evenness is no longer enforced. The bound still excludes count $3$, which would need $x=3/2$$3/2$. If those bounds are also removed, every count $c$ can be matched by $x=c/2$$c/2$. An odd count is required by writing $2x+1$$1$, and more decisions need a larger integer range for $x$.

Key Results¶

• When $x=0$$0$, all three decisions are no.
• When $x=1$$1$, exactly two decisions are yes.
• Allowing $x$ to be continuous would remove the parity restriction.

Examples¶

• $(y_1,y_2,y_3)=(1,1,0)$ is allowed with $x=1$$1$.
• $(1,1,1)$ is excluded because it would require $x=3/2$$3/2$.

Prerequisites¶

• Binary Variable

Related Concepts¶

• Finite-Value Constraint
• Contingent Decisions

Sources¶

• OR Modelling · Week 3

Symbols: element of

Last updated: 27 October 2026 11:52