3
$\begingroup$

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: enter image description here

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. enter image description here

enter image description here

$\endgroup$
3
$\begingroup$

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}

| improve this answer | |
$\endgroup$
  • $\begingroup$ I have added a more explanation in my answer and attempted to apply your solution to it. $\endgroup$ – Sam Apr 12 at 10:07
  • $\begingroup$ My answer applies to case 1. $\endgroup$ – RobPratt Apr 12 at 12:23
  • $\begingroup$ 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. $\endgroup$ – Sam Apr 12 at 13:49
3
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer. I have provided a more detailed example in the question. Does your solution still hold? $\endgroup$ – Sam Apr 12 at 10:06
  • $\begingroup$ 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. $\endgroup$ – prubin Apr 13 at 15:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.