5

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.

yucelf
  • 53
  • 4
  • 2
    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? – Joris Kinable Aug 18 '21 at 15:44

1 Answers1

5

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.

Joris Kinable
  • 3,451
  • 8
  • 19
  • 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? – yucelf Aug 18 '21 at 17:49
  • 1
    @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$. – Joris Kinable Aug 18 '21 at 18:00