Why does a Max constraint work, but this non-negativity constraint does not?

Question

Suppose I have the following constraint: \begin{align}x_{t} &= x_{t-1} + y_{t-1} - z_{t-1}\\x_{t} &\ge 0\end{align}

From my limited experience in coding my own problem, I have found that my model becomes infeasible if I impose the non-negativity constraint on $ x_{t} $ because what happens is the $z_{t-1}$ term begins to overpower the other two positive terms and the non-negativity constraint just does not hold, ultimately resulting in infeasibility.

However, if I reformulate the problem as: $$ x_{t} = \max\{x_{t-1} + y_{t-1} - z_{t-1}, 0 \} $$

and then perform a linearization on this formulation, I can run the model and get the desired result of the non-negativity constraint.

So it seems strange to my naive eye that reformulating the problem as a max constraint and then doing a linearization ~ which seems to be a much more complicated route ~ will work for me, but the non-negativity constraint does not. At least to me, formulating the constraint as a linear relation with a non-negativity constraint and then as a 'max' are essentially the same thing.

Clearly, they are not, but why not? Part of me feels like this could be a 'solver' problem, but i'm hoping there is a more theoretical way of understanding.

Answer 1

A rigorous way to look at this problem is to consider the polyhedra corresponding to your constraints (I linearized the 'max' for the second one):

$$P_1 = \left\{(x_t,x_{t-1},y_{t-1},z_{t-1}): x_t = x_{t-1}+y_{t-1}-z_{t-1}, x_t \geq 0 \right\}$$ and $$P_2 = \left\{(x_t,x_{t-1},y_{t-1},z_{t-1}): x_t \geq x_{t-1}+y_{t-1}-z_{t-1}, x_t \geq 0 \right\}.$$

In your answer you state that the two sets of constraints are "essentially the same thing", which would formally mean that $P_1=P_2$. However, we can observe that while $P_1\subseteq P_2$, it is not true that $P_2\subseteq P_1$ as e.g. the point $(0,0,0,1)$ is an element of $P_2$ but not of $P_1$. So actually, $P_1$ is a proper subset of $P_2$, which is why it is possible that the first set of constraints gives you an infeasibility, while the second does not.

Answer 2

I think it is helpful to analyze the situation from a practical point of view. Please note that your constraint is of the general form of linear control constraints, arising in many practical problems such as inventory control, production planning, and finance. In such applications, you are relating the current variable level, $x_t$, to the previous variable level, $x_{t-1}$, via some activities (e.g., subtraction of demand, $z_t$, and addition of new production, $y_t$). In such case, it is possible that $z_t \gt x_{t-1} + y_t$, which would result in $x_t$ becoming negative. This would be infeasible due to the constraint $x_t \ge 0$. From the practical POV, negative $x_t$ is equivalent to shortage (i.e., not having enough product to satisfy the customer's demand), while positive $x_t$ corresponds to surplus (i.e., having more inventory than required and being forced to keep it in your own warehouse). To allow for shortages, you could rewrite $x_t$ as $x_{t}^{+} - x_{t}^{-}$ with $x_{t}^{+} \ge 0$ and $x_{t}^{-} \ge 0$. This would make your original constraint rewritten as follows: $$x_{t}^{+} - x_{t}^{-} = x_{t-1}^{+} - x_{t-1}^{-}+y_{t-1}-z_{t-1}.$$

If you intend to allow for shortages, the above constraint is what you need (in the inventory control literature, this is referred to as inventory control with backlog). If not, your second constraint is the way to go (in the inventory control literature, this is referred to as inventory control with lost sales). Of course, this is to be determined based on your problem definition and application.

PS. Depending on your whole model, it might be incorrect to linearize $ x_{t} = \max\{x_{t-1} + y_{t-1} - z_{t-1}, 0 \} $ simply as $ x_{t} \ge x_{t-1} + y_{t-1} - z_{t-1}$ and $x_t \ge 0$. Suppose that the inventory cost is smaller that the production cost. This might result in $x_t$ being greater than $x_{t-1} + y_{t-1} - z_{t-1}$, while you want $x_t$ to be exactly equal to $x_{t-1} + y_{t-1} - z_{t-1}$. Hence, you might need to linearize the $\max$ constraint using binary variables (you could find the method for doing this with a little search on the web).