15
$\begingroup$

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?

$\endgroup$
18
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – GrayLiterature Oct 19 '19 at 15:27
  • $\begingroup$ @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. $\endgroup$ – LarrySnyder610 Oct 20 '19 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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