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.

So good job!!!

ReplyDeleteHi, Paul. Is there any approach to model the strict inequality in CPLEX?

ReplyDeleteOnly for inequality of integer expressions (and that's true of all MIP solvers, not just CPLEX).

DeleteWhat if $d=0$ can we still model $z=1 \iff x>0$ ? Thanks.

ReplyDeleteYes, there is nothing special about $d$ being zero. You still have to specify a positive value of $\epsilon$ and live with the ambiguity that when $0 < x < \epsilon$, $z$ can be either 0 or 1.

Delete