Logical Indicators in Mathematical Programs

There's a common paradigm in many procedural programming languages that expressions involving relational operators spit up a true/false value that either is coded numerically (typically 1 for true, 0 for false) or will automatically be translated by the compiler/interpret that way. So, for example, the expression "a*(b>c)" produces the value a if b>c and 0 otherwise. Unfortunately, newcomers to mathematical programming are sometimes inclined to attempt that in the context of a mathematical programming model. Unless they are using an unusually clever modeling language -- more clever than any I've used -- it will not work (and even with a very clever modeling language it will not work for strict inequalities). There are ways to do what is wanted, but they involve introducing binary variables (and additional constraints), and you may not always get exactly what you wanted.

As a simple example, let's say that I have a variable $x$ that represents the delivery time for an order, and a parameter $d$ which is the due date for the order. I have a model in which I minimize some cost function $f(\cdots)$, and I want to assess a fixed penalty $p$ (another parameter) if, and only if, the order is late ($x>d$). In this example, the penalty is a constant, not dependent on how late the order is. Writing a computer program, I might be tempted to try something like $f+=p*(x>d)$, but that will not come close to flying in an optimization model. So my first step is to introduce a new binary variable $z\in\{0,1\}$ which will (hopefully) take the value 1 if the order is late and 0 if not. The objective then becomes $\textrm{maximize }f(\cdots)+p*z$.

Now I need to constrain $z$ so that it takes the correct values. In this particular example, I get some indirect assistance from the objective function. Assuming $p>0$ (I'm not rewarding tardiness), the solver will always choose $z=0$ over $z=1$ given the rest of the solution (meaning once $x$ is known). So it does not matter if the formulation allows both $z=1$ and $z=0$ when $x\le d$; the solver will choose $z=0$ in that case to reduce the objective value. Therefore I only need to incorporate a constraint that says $x>d\Longrightarrow z=1$; I don't need to worry about what happens when $x\le d$. The strict inequality might pose a problem, but fortunately the contrapositive $z=0\Longrightarrow x\le d$ contains a weak inequality.

Now I'm on the home stretch. I need to come up with an upper bound $M>0$ on the possible tardiness of the order. I add the constraint \[x\le d + M*z.\] If it turns out the order is late ($x>d$), this will force $z=1$ (so I'm charged the penalty) and the constraint will become $x\le d+M$, which is nonbinding as long as I chose $M$ sufficiently large. If it happens that the order is on time ($x\le d<d+M$), then $z$ can take either value, and I rely on the objective function to cause the solver to choose $z=0$.

What if I need $z=1$ if and only if $x>d$, and I cannot rely on the objective function (because, let's say, there is no cost penalty for $z=1$)? With one exception, it cannot be done in a mathematical program ... but I can come close. I need another constant $L>0$ such that $d-L<x$ for any feasible value of $x$. (In our example, $L$ bounds the earliness of the order.)  Now I have two choices. The first is to add a pair of constraints:\begin{eqnarray*}x\le d + M*z\\ x\ge d - L*(1-z).\end{eqnarray*} Now $x>d\Longrightarrow z=1$ and $x<d\Longrightarrow z=0$. If $x=d$, though, $z$ can take either value.

The alternate approach involves yet another constant, this time a small one ($\epsilon>0$). Think of $\epsilon$ as representing the minimum discernible difference between $x$ and $d$. The defining constraints for $z$ are now \begin{eqnarray*}x\le d + M*z\\ x\ge d + \epsilon - (L+\epsilon)*(1-z).\end{eqnarray*} What we get is $x\ge d+\epsilon \Longrightarrow z=1$ and $x\le d\Longrightarrow z=0$. What we sacrifice is that $d<x<d+\epsilon$ is now infeasible. In our example, it is illegal to be very slightly late; if the order cannot be on time, it will have to be at least $\epsilon$ time units late. If you're thinking "cool, I can pick $\epsilon=10^{-50}$", keep in mind that $\epsilon$ has to be large enough that it does not get lost in rounding error in the solver (otherwise you're back to the first case, where delivery close to the due date allows $z$ to go either way).

I mentioned one exception above. If $x$ (and $d$) are integers, life is easy, because $x>d$ is equivalent to $x\ge d+1$. So in this case we can get exactly what we want, using the second approach with $\epsilon$ slightly smaller than 1.