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