0
$\begingroup$

I have an integer programming problem:

max $F = −4x_1 + 3x_2$

subject to:

  • $−x_1 + 3x_2 ≤ 9$
  • $7x_1 − 3x_2 ≥ −7$
  • $x_1 ≤ 3, x_2 ≥ 0$, and integer valued

How can I model the restriction that $x_1 > 2$ and $x_2 > 3$ cannot both hold at the same time?? I'm told to give explicit numerical values for any “Big M” that I use.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Introduce binary variables $y_1$ and $y_2$ and impose linear big-M constraints: \begin{align} x_1 - 2 &\le M_1 y_1 \tag1 \\ x_2 - 3 &\le M_2 y_2 \tag2 \\ y_1 + y_2 &\le 1 \tag3 \\ \end{align} Constraint $(1)$ enforces $x_1 > 2 \implies y_1 = 1$. Constraint $(2)$ enforces $x_2 > 3 \implies y_2 = 1$. Constraint $(3)$ enforces $\neg (y_1 \land y_2)$.

You want $M_1$ to be an upper bound on $x_1 - 2$ when $y_1=1$, so take $M_1 = 3 - 2 = 1$. To determine a good value for $M_2$, first use the original constraints to deduce an upper bound on $x_2$.

$\endgroup$
3
  • 1
    $\begingroup$ Hello, is it possible to include an explanation on how to find the upper bound M1 and M2 ? $\endgroup$ Commented Nov 5, 2020 at 4:37
  • $\begingroup$ @RobPratt how would we find the bound $M_2$ in this case? $\endgroup$ Commented Nov 6, 2020 at 11:03
  • $\begingroup$ By your first constraint and the upper bound on $x_1$, we can deduce that $3x_2\le 9+x_1\le 9+3=12$, so $x_2\le 4$. Now you want $M_2$ to be an upper bound on $x_2-3$, so take $M_2=4-3=1$. $\endgroup$ Commented Nov 6, 2020 at 13:51

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.