# Use of comparisons in objective function of an ILP

If the objective function of a problem contains a comparison between two linear statements, can the problem still be defined as an Integer Linear Program? For example:

$$\text{max} \sum_{\forall i,j} x_{i,j} - (y_{i,j}\cdot A_{i,j} \ge B_{i,j})$$ where $$x_{i,j}$$ and $$y_{i,j}$$ are binary variables, and $$A_{i,j}$$ and $$B_{i,j}$$ are constants.

Note: The value of $$(y_{i,j}\cdot A_{i,j} \ge B_{i,j})$$ should be 1 if it evaluates to true, 0 otherwise.

• What is the outcome of $(A_{ij}y_{ij} \geq B_{ij})$? If this expression is satisfied, do you want to count it as a 1 or as a 0? Aug 18 '21 at 15:44

You would have to introduce a helper variable (say $$z_{ij}$$) to count:
\begin{align} \text{max }& \sum_{\forall i,j} x_{i,j} - z_{ij} &\\ \text{s.t. }& A_{i,j} y_{i,j} \leq B_{i,j} + Mz_{ij}&\forall i,j\\ &z_{ij}\in \{0,1\} &\forall i,j \end{align}
Here $$M$$ is a sufficiently large number.
• If $A_{i,j} y_{i,j} = B_{i,j}$, $z_{i,j}$ would need to be 1, but this formulation seems to yield $z_{i,j}=0$. Am I wrong? Aug 18 '21 at 17:49
• @yucelf yes the border case of equality is a little tricky. You could change the equation to $A_{ij}y_{ij}\leq B_{ij}-\epsilon + Mz_{ij}$ where $\epsilon$ is a small number, e.g. $0.00001$. Aug 18 '21 at 18:00