Difference between constraint formulation and performance

Question

I am wondering about the characteristics and performance of some constraints with only binary variables. I assume that solving (integer) linear programs is faster than quadratic ones.
At first: $$ a,b,c \in \{0,1\} \\ a\cdot b = c \tag{1} $$ Is it a quadratic constraint because of the multiplication with two variables.
I try to model the logical equation $ a \land b = c $ and wonder about the performance of equation 1 or 2 (linearization of AND-Constraint, Chapter 2.5). \begin{align} c &\le a \\ c &\le b \\ c &\ge a+b-1 \tag{2} \end{align} Which one should I use and why (please considering performance)?

Second:
What is the difference between equation 3 and 4 for the logical equation $ a = 1 \rightarrow b = c$ with $ a \in \{0,1\}; b,c \in \mathbb{N}$? From a logical/mathematical point of view, I do not see anyone. $$ a \cdot b = a\cdot c \tag{3} $$

\begin{align} b-a\cdot M &= c-a\cdot M \tag{4} \end{align}

Summary of the questions:

1. Is there a performance issue between $(1)$ and $(2)$?
2. Which equation ($(3)$ or $(4)$) should I use and why?

If you know a good resource that explains these basics, please let me know.

Answer 1

Instead of deciding between linear and nonlinear (quadratic) constraints, I think one should rather decide in terms of convexity as a rule of thumb. For integer problems, one should decide in terms of the convexity of the continuous relaxations. Convex problems are much easier to solve than non-convex problems since (for a convex minimization problem) each local minimizer is guaranteed to be a global one.

Note that you obtain the continuous relaxation of a problem by replacing all discrete sets with contiguous sets. For instance, in your case, you'd replace the discrete set $\{0,1$} with the contiguous set $[0, 1]$. Note also that a MIP solver always solves multiple instances of continuous relaxations during a Branch&Bound algorithm, so it's highly recommended to preserve a nice mathematical structure of the continuous relaxations if possible. Last but not least, a quadratic equality constraint is always non-convex and a linear constraint is convex, regardless of whether it is an inequality or an equality constraint.

To answer your questions:

1. The continuous relaxation of constraint (2) is convex, while (1) is not. So I'd pick constraint (2).

2. The continuous relaxation of constraint (4) is convex, while (3) is not. So I'd pick constraint (4).

Answer 2

The answers to the questions may be solver dependent, because many solvers (including I think all the commercial ones) will either linearize the products of variables or perhaps bake them into the branching scheme.