3
$\begingroup$

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?

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Commented Jan 30 at 14:43

2 Answers 2

3
$\begingroup$

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}

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.