1
$\begingroup$

I have the following problem $$\begin{align*} & \min \ f(X) \newline & X = \begin{cases} 1&; x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3, \newline 0&; \text{otherwise}. \end{cases} \newline & \text{where } X \in \{0,1\}. \end{align*}$$ Following this argument, we write $$ \begin{align*} & \text{If } x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3, \text{ then } X=1, \newline & \text{if } \sim \{x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3 \}, \text{ then } X=0. \end{align*} $$ Here $\sim \{\} $ implies that at least one constraint is not satisfied. The contrapositive of the above statement is $$ \begin{align*} &\text{If } X=0, \text{ then } \sim \{x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3 \} \text{ (i)}, \newline & \text{if } X=1, \text{ then } \{x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3 \} \text{ (ii)}. \end{align*} $$ In order to write the indicator constraint as an integer program, we fix a very large $M$. The condition (ii) can be written as \begin{align*} \text{(iii) } x_1 - c_1 \leq M(1-X), \newline \text{(iv) }x_2 - c_2 \leq M(1-X), \newline \text{(v) }x_3 - c_3 \leq M(1-X). \newline \end{align*}
To write condition (i), we choose a very small $\epsilon>0$ and consider $x_1 > c_1$ to be the same as $c_1 - x_1 + \epsilon \leq 0$. Then we define $X_1, X_2, X_3 \in \{0,1\}$ such that $$ \begin{align*} \text{(vi) } c_1 - x_1 + \epsilon \leq (M+\epsilon)X_1, \newline \text{(vii) } c_2 - x_2 + \epsilon \leq (M+\epsilon)X_2, \newline \text{(viii) } c_3 - x_3 + \epsilon \leq (M+\epsilon)X_3, \newline \text{(ix) } X_1 + X_2 + X_3 \leq 2+X, \newline X \leq MX_1, \newline X \leq MX_2, \newline X \leq MX_3. \end{align*} $$ So when $X =1$, the last 3 constraints force $X_1, X_2, X_3 = 1$, thereby making (vi-viii) redundant and (iii-v) are satisfied. When $X=0$, (iii-v) become redundant, and (ix) force at least one of $X_1,X_2,X_3$ to be $0$.
The above is what I tried; any scope for improvement? Any idea or reference will also be of great help.

$\endgroup$

1 Answer 1

2
$\begingroup$

In your final three constraints, you can take $M=1$, yielding $X \le X_i$.

For (iii) through (v), you can strengthen the formulation by replacing $X$ with $X_i$ because $1-X_i \le 1-X$.

For all the big-M constraints, you should use a constraint-dependent value of $M$.

$\endgroup$
5
  • $\begingroup$ Does "constraint-dependent value of M" indicate $M = \max_{i = 1,2,3} |x_i - c_i|$? $\endgroup$ Commented Nov 6, 2023 at 5:41
  • $\begingroup$ No, I mean a possibly different value of $M$ for each constraint. For example, in (iii) you should take $M$ to be an upper bound on $x_1-c_1$. $\endgroup$
    – RobPratt
    Commented Nov 6, 2023 at 11:54
  • $\begingroup$ Thank you for the reply. But I am wondering why M must differ with constraints. Why the same M cannot work? $\endgroup$ Commented Nov 8, 2023 at 4:25
  • $\begingroup$ And it must be an upper bound for $|x_1 - c_1|$, right? $\endgroup$ Commented Nov 8, 2023 at 10:16
  • $\begingroup$ Yes, you can use the same $M$ for all constraints, but a best practice is to use the smallest possible value for each constraint. For (iii), $M$ should be an upper bound on $x_1-c_1$ when $X_i=0$. $\endgroup$
    – RobPratt
    Commented Nov 8, 2023 at 13:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .