Integer program in which at least one of three inequalities holds

1k Views Asked by At

Formulate the following Integer Program considering alternative constraints

\begin{align}\max \qquad &2x-79y\\[0.2cm]\text{ subject to}\qquad& 0\le x\le 20 \, \text{ and }\, 0\le y\le 30\end{align}

and at least one of the following inequalities holds: \begin{align}-2x+3y&\ge 0\\[0.2cm]5x-4y&\ge0\\[0.2cm]7x+8y&\le40\end{align}

1

There are 1 best solutions below

2
On BEST ANSWER

As Jimmy says, it is a pretty badly designed example, as the intersection of the complement of the constraints is empty so some constraint will always hold.

However, I think the problem designer (your teacher?) wants you to create a big-M model. To ensure N of the constraints $f_i(x)\leq 0$ to hold, you can write it as $f_i(x)\leq M(1-\delta_i)$ where $\delta_i$ is binary, and then introduce a suitable constraint on $\delta$, and select a suitable constant $M$ to make the model valid (details left to the student)