How to formulate (linearize) a maximum function in a constraint?

Question

How to formulate (linearize) a maximum function in a constraint? Suppose $C = \max \{c_1, c_2\}$, where both $c_1$ and $c_2$ are variables. If the objective function is minimizing $C$, then it can be simply done by applying $C \geqslant c_1$, and $C \geqslant c_2$. But if the objective function is non-regular, e.g. earliness tardiness, the value of $C$ will be larger than the maximum of $c_1$ and $c_2$. So my question is how to formulate it correctly?

Answer 1

(I'm going to change $c$ to $x$ in my answer, since $c$ is usually used for cost coefficients, not decision variables.)

We want a set of constraints that enforces $X = \max\{x_1,x_2\}$. Define a new binary decision variable $y$, which will equal 1 if $x_1 > x_2$, will equal 0 if $x_1 < x_2$, and could equal either if $x_1 = x_2$. Let $M$ be a constant such that $x_1,x_2 \le M$ in any "reasonable" solution to the problem.

The following constraints enforce the definition of $y$: $$\begin{align} x_1 - x_2 & \le My \\ x_2 - x_1 & \le M(1-y) \end{align}$$ Then, the following constraints enforce $X = \max\{x_1,x_2\}$: $$\begin{align} X & \ge x_1 \\ X & \ge x_2 \\ X & \le x_1 + M(1-y) \\ X & \le x_2 + My. \end{align}$$ The first two constraints say $X \ge \max\{x_1,x_2\}$, as you suggested in the question. Combined with these constraints, the last two constraints say that $X = x_1$ if $x_1 > x_2$ (so $y=1$) and $X = x_2$ if $x_2 > x_1$ (so $y=0$).

---

UPDATE: @EhsanK correctly pointed out to me that the first 2 constraints are not necessary. The 4 remaining constraints are sufficient to enforce the definition of $y$, and therefore of $X$.

---

Related:

• For more on logical constraints, see In an integer program, how I can force a binary variable to equal 1 if some condition holds?.
• For more on big-M, see Why is it important to choose big-M carefully and what are the consequences of doing it badly?.
• For a similar constraint, see How to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-side. But note that in that question, only an inequality constraint is required for $X$, not an equality constraint.