# Mocking up conditional statements in LP

I would like to know how if condition statements in linear programming can be reformulated using indicator constraints, and hence solved as a mixed integer linear program. Specifically:

1. Is it possible to formulate the problem below using indicators constraints, without using big-M? If so, how? I know that some solvers do it automatically but I am interested in doing it manually
2. How to formulate it using big-M?

Assume that the problem is given by:

For a more detailed example, assume that you have certain obligation at times 1, 2 and 3. You have 10 assets. First you want to see if you can meet the obligations by the first 5 assets before considering the remaining 5. The objective is to find the minimum amount of asset that you can invest in to meet the obligations.

## 2 Answers

It sounds like you want to enforce the following logical proposition: $$\bigvee_{i=6}^{10} (x_i>0) \implies \bigwedge_{j=1}^{5} (x_j=1)$$

You can model this by introducing a binary variable $$y$$ and linear constraints: \begin{align} x_i &\le y&&\text{for i\in\{6,\dots,10\}}\\ y&\le x_j &&\text{for j\in\{1,\dots,5\}}\\ \end{align}

• I have added a more explanation in my answer and attempted to apply your solution to it.
– Sam
Commented Apr 12, 2020 at 10:07
• My answer applies to case 1. Commented Apr 12, 2020 at 12:23
• Thank you. I suspect case 2 can only be dealt with big-M formulation and only if xi>0 for i=1,..5 though I am not sure.
– Sam
Commented Apr 12, 2020 at 13:49

The answer to the first part is yes, provided that you are using a solver that supports indicator constraints. As far as I know, there is no "standard" notation for it. Something like $$a_1 x_1 \le b \implies x_2 = 0$$would seem reasonable to me. The "else" part is tricky, since it deals with the case $$a_1 x_1 > b$$ and strict inequalities are a no-no. You could approximate it by $$a_1 x_1 \ge b + \epsilon \implies x_1 = (1,\dots,1)^\prime$$where $$\epsilon > 0$$ is some small tolerance value. Note that this would make any solution with $$b < a_1 x_1 < b + \epsilon$$ infeasible.

A big-M formulation for the simplified version might look like the following, where $$y\in\lbrace 0, 1\rbrace$$ is a new binary variable, $$M_1$$ is a valid upper bound on $$a_1x_1$$ and $$M_2$$ is a valid upper bound on $$b+\epsilon - a_1x_1$$: $$\begin{equation*} a_1 x_1 + a_2 x_2 \le b \\ a_1 x_1 \le b + M_1y \\ a_1 x_1 \ge b + \epsilon - M_2(1-y) \\ x_2 \le y \\ x_1 \ge y \\ 0 \le x_1, x_2 \le 1. \end{equation*}$$ There is one important catch here. This only works if $$a_1 \ge b+\epsilon$$.

• Thank you for your answer. I have provided a more detailed example in the question. Does your solution still hold?
– Sam
Commented Apr 12, 2020 at 10:06
• Not for case 2. I'm not sure if it can be fixed for case 1, but it's probably not worth it. There could be a problem if the second tier variables are much cheaper than the first tier variables. It's much easier (and arguably safer) to solve a restricted LP (second tier variables locked at zero) and then solve the full problem only if the restricted problem is infeasible.
– prubin
Commented Apr 13, 2020 at 15:59