# How To Linearize $X = \max\{x_1,x_2\}$

I am new to thinking about math programming and I have a particular constraint I am hoping to reformulate, I just don't know the proper mathematical translation for what I am hoping to do. Enforcing the non-negativity constraint on $$X$$ in Constraint (1) seems to make my model infeasible, and so I am hoping that with a reformulation of my problem the solver I am using (knitro) will be able to report feasibility.

My original constraint looks like this:

$$X_{t} = X_{t-1} + aY_{t-1} - Z_{t-1}, \quad t\in[1,T] \tag1 \\X_{t} \ge 0 \\ \\ X_{0}, Y_{0}, Z_{0} \ge0$$

The way that I am thinking about the new formulation is shown in Constraint (2), but I feel that this is where I will need some correction on the formulation:

$$X_t = \begin{cases} 0, & \text{if} \quad X_{t-1} + aY_{t-1} - Z_{t-1} \le 0 \\ X_{t-1} + aY_{t-1} - Z_{t-1}, & \text{otherwise} \end{cases} \tag2 \\t\in[1,T] \\ X_{0}, Y_{0}, Z_{0} \ge0$$

I apologize if this is straightforward, I just don't know the precise wording to Google my problem because this is not my field of study.

If someone would be able to (1) help me classify what type of constraint this would be called and possibly a way to linearize it or a useful resource I can follow up on, I would be appreciative of that.

• If your $t$ index starts from 1, what happens to $X_{t-1}$? Do you have an initial value for your first (or here, zeroth) index? – EhsanK Oct 8 '19 at 13:28
• @EhsanK I updated the problem formulation. But you are correct, t starts from 1 and there are initial values supplied so that X_(t=1) would exist. – GrayLiterature Oct 8 '19 at 13:48
• If $a$ is a parameter (not a decision variable) then constraint (1) is linear, and constraint (2) is not. So constraint 91) should be the way to go. If you are finding that your model is infeasible, it is not due to any nonlinearity, but due to something else in your model or your data. – LarrySnyder610 Oct 8 '19 at 13:57
• Your first formulation would result in infeasibility if any $X_t$ came out $< 0$. Your 2nd formulation amounts to $X_{t} = \text{max}( X_{t-1} + aY_{t-1} - Z_{t-1},0)$. plus any constraints on the Y 's and Z 's. The best way to handle that depends on the rest of the model and on the solver. – Mark L. Stone Oct 8 '19 at 14:02
• Edit to my comment: Didn't see @Larry comments before mine. Yes, you can do per his link, which requires bnary variables which KNITRO can handle, but if the overall model (excluxding binaries) is not convex, KNITRO's solution will be heuristic (could be totally "wrong"). Other approach is depending on front end used, directly implement max, and hope to blast through any non-diffeerentiabilities. – Mark L. Stone Oct 8 '19 at 14:12

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$$).