Simplex and mathematical models: Truncating expresion to 0 if negative

Question

Is there a simplex compatible way to model an expression that "truncates" (sorry for not finding a better word for it) the value to 0 if it turns negative?

I have the following restrictions: $$t_{i,k} \le k - h_i \forall i \in I , k \in K$$ $$t_{i,k} \in (0,1)$$ $$h_i \in \mathbb{N}$$

Where K is a subset of $\mathbb{N}$

What i want to do is convert the right part of the first restriction, $k-h_i$, to 0 when it becomes negative, in other words, make $t_{i,k} \le \max(k-h_i,0)$

¿Is it posible? Thanks

Answer 1

I've found another way to solve this problem, yet has slightly different implications: Change the restriction to $$M(t_{i,k}-1) \le k - h_i$$ That way, the algorithm must choose:

1) If it wants to turn on the variable $t_{i,k}$, the restriction must check $0 \le k - h_i$.

2) If not, then the restriction $-M \le k-h_i$ holds for any value of $k$ and $h_i$, given an appropriate value of M

The difference with your solution @holger3000 is that this is more relaxed in the way that it will let $t_{i,k}$ be 1 even if the right side becomes a fraction of 1. For instance, if $k - h_i = 0.4$ then $t_{i,k}$ can still be 1 since the restriction will hold. This is not the case with your solution.

Either will work with my problem (since K are also integers, i did not explicit that in my original problem), but i found it was interesting to propose this solution as well.

Answer 2

First of all, since the variable $t_{i,k}$ is binary already, the constraints you show are not actually "simplex compatible" - you have a mixed integer program and probably use branch-and-bound. However, simplex is used to solve the LP relaxations of the problem at the nodes of each branch.

You can use either-or constraints using the Big M method from integer programming in order to get the result you want. Introduce binary variables $b_{i,k}$ and a sufficiently large constant $M$, then add the following constraints.

$k-h_i \leq t_{i,k} \leq k - h_i + M(1-b_{i,k})\\ t_{i,k} \leq Mb_{i,k}\\ t_{i,k} \geq 0$