I am interested in a mathematical program with objective:
$\max \sum_{i \in I} x_i $
where $x_i$ is a binary defined variable as follows:
$x_i = 1$ if $y_i - A \geq 0$
$x_i = 0$ if $y_i - A < 0$
where $y_i$ is a real or integer variable, and $A$ is a constant. I am not able to express such a constraint.
My first thought was a constraint like:
$x_i \leq y_i - A +1$
but it works only if $y_i \geq A$. If the difference is negative it does not work.
I hope this can be expressed as a linear program. Thanks
You're on the right track, just have to keep going.
$x_i = 1$ if $y_i - A \leq 0$
$x_i = 0$ if $y_i - A > 0$
Which is the same as
$x_i = 1$ if $y_i \leq A$
$x_i = 0$ if $y_i > A$
Now, I'll follow up what you were doing. We can try to find another solution later, but I want to show a way of using what you've discovered to get to find the answer.
You've find this constraint, which you say it works only when $y_i \geq A$
That's fine, but remember we need it to work for $y_i > A$
$x_i \leq y_i - A - 1$
If $y_i > A$, I'll say $y_i = A + surplus$ then
$x_i \leq A + surplus - A -1$
$x_i \leq surplus - 1$
This doesn't help us in that case, because this inequation would only work if the surplus is between 1 and 2. Remembering that we want to force a 0 on $x_i$ on this case.
Then again if we could just at least force the 0 on this case, we would be closer to achieving what we want. How can you force the 0 ? There are probably many ways. I'll write one that I've just thinked, it's probably not the best, but it'll work, we can think later how to improve how it looks.
I'll start easy, with something that looks like what you were doing. We will focus on setting the 0 when $y_i \leq A$
Then this is my first attempt: $$x_i \leq y_i - A$$
If $Yi \leq A$ then it should do nothing. We check that, and it's not true when the difference is less than 1. Then we correct that.
$$x_i \leq y_i - A + 1$$
Now we have something which does nothing when $yi > A$, but in the case we want to force the 0, we can reach something like $xi \leq -1$ which is not nice.
So i' say, that's fine, that equation is valid, but if that one is telling you to set that variable to something negative, let it be a 0 because if not, this won't have a solution.
Let M be a big enough number, in this case, M could be 2. Let U be a bivalent variable-
$$x_i \leq y_i - A+ 1 + M*U$$ $$x_i \leq 0 + (1-U)* M$$
Now since $x_i$ can't be less than 0, on a negative number on the first equation, the second is forced to be active, and the first is forced to be inactive.
In other cases you have an interval where it's the same which one is active. And another one where both can be. When both can be, the important thing is that the less restrictive constraint can be picked. We will use that to force the 1 on the other case.
Setting a 1 can always be a little bit easier than a 0. We can do that with only one constraint. As always, there are other ways, this is one which is really easy, but has some drawbacks. In theory every M big enough can work. Because of the limitations of a computer, you have to avoid having a variable too close to 0 because the computer could just say it's 0. In a real work, you have to pay attention with what M to pick. If it's too big the computer gives you trouble, if it's too little the math won't work.
$x_i > (A - y_i)/M_2$
When $y_i > A$ it sets a 1 on $x_i$ and in the other case it does nothing.
Now the only thing left is to "fuse" those equations. In this case, it's only putting all of them together.
$$x_i \leq y_i - A+ 1 + M*U$$ $$x_i \leq 0 + (1-U)* M$$ $$x_i \geq (y_i - A)/M_2$$
Now, when we have all the equations, it's good to check what happens on the limit between both sets. In this case, when $y_i = A$.
We can see that when $y_i = A$ the first set does nothing, and the other one does nothing. So we have a little trouble. Usually to fix this you can use a little constant $\epsilon$
$$x_i \leq y_i - A+ 1 + M*U$$ $$x_i \leq 0 + (1-U)* M$$ $$x_i \geq (y_i + \epsilon - A)/M_2$$
That'd be all. If you need another approach, there are some general solutions to this kind of problems on some book. The second equation I used is not usually the most common approach, feel free to use another one you know. Or ask again if you need other one.
Something extra: To simplify this kind of problems, you can also take a look on what you're optimizing. Let's say that in your problem it's always better to have a 0 than a 1. Then you can just forget about setting the 0, and just use an equation to set the 1.