Mocking up conditional statements in LP

Question

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.

Answer 1

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}

Answer 2

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$.