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

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?

(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:

• Is there a particular name for this transformation? I am trying to find some type of academic source that I can reference this from for a paper I am working on. Oct 19, 2019 at 15:27
• @D.Gray Maybe, but I don't know of one. It's just a standard(ish) trick. If you really want to find a standard name, you could post that as a new question. Oct 20, 2019 at 0:48