# Convex equivalent of a constraint

I have a constraint as follows in my MILP model:

$$\sum_{e} (a_1(e) - a_2(e))^2 \leq M$$

Where, $$a_1(e)$$ and $$a_2(e)$$ are binary variables. Would you please guide me how can I find the equivalent convex constraints to put in the model and solve it by GAMS/CPLEX?

• Without commenting on the merits of the answers or whether various solvers automatically reformulate the binary quadratic constraints to linear, the constraints as written are already convex (quadratic), and can be handled as such by CPLEX. Jan 30 at 14:43

## 2 Answers

If $$a_1$$ and $$a_2$$ are binary, then $$y=(a_1 - a_2)^2$$ is also binary.

More precisely: $$a_1 \wedge a_2 \implies \neg y \quad \equiv \quad \neg(a_1 \wedge a_2) \vee \neg y \quad \equiv \quad \neg a_1 \vee \neg a_2 \vee \neg y\\ \neg a_1 \wedge a_2 \implies y \quad \equiv \quad \neg(\neg a_1 \wedge a_2) \vee y \quad \equiv \quad a_1 \vee \neg a_2 \vee y\\ a_1 \wedge \neg a_2 \implies y \quad \equiv \quad \neg(a_1 \wedge \neg a_2) \vee y \quad \equiv \quad \neg a_1 \vee a_2 \vee y\\ \neg a_1 \wedge \neg a_2 \implies \neg y \quad \equiv \quad \neg(\neg a_1 \wedge \neg a_2) \vee \neg y \quad \equiv \quad a_1 \vee a_2 \vee \neg y$$

So you can replace your constraint with $$\sum_e y(e) \le M \\$$ and linear equations \begin{align} 1-a_1(e)+1-a_2(e)+1-y(e) &\ge 1 \\ a_1(e)+1-a_2(e)+y(e) &\ge 1 \\ 1-a_1(e)+a_2(e)+y(e) &\ge 1 \\ a_1(e)+a_2(e)+1-y(e) &\ge 1 \\ \end{align}

Introduce $$d(e) \in \{0, 1\}$$(or $$[0, 1]$$), $$\forall e$$. \begin{aligned} -d(e) \leq a_1(e) - a_2(e) &\leq d(e)\\ \sum_e d(e) &\leq M \end{aligned}

Notice that we only need $$d(e) \geq (a_1(e)-a_2(e))^2$$ (rather than "$$=$$"). So logically we only need $$\left((a_1 \wedge \neg a_2) \vee(\neg a_1 \wedge a_2)\right) \Rightarrow d$$