10
$\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$
  • $\begingroup$ Do you know an upper bound on $c_1$ and $c_2$? $\endgroup$ – LarrySnyder610 Jun 24 at 3:45
  • $\begingroup$ Actually $c_1$ and $c_2$ are both variables and we have no tight bound on them. $\endgroup$ – Mostafa Jun 24 at 3:48
12
$\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$).

Related:

$\endgroup$

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.