Integer Programming with Binary Variables.

binary-programminginteger programmingoptimization

Question :
A company wants to form three different teams $A, B, C$ from a pool of 7 employees, which we represent as the set $E=\{1, \ldots, 7\}$. Each employee $i$ has a certain number of years $\alpha_{i}$ of experience at the company, and has $\beta_{i}$ as their current annual salary. Note that $\alpha_{i}, \beta_{i}$ are constants, but you may assume that $0 \leq \alpha_{i} \leq 10$ and $0 \leq \beta_{i} \leq 100000$.
We define binary variables $x_{i j}$ for all $i \in E$ and $j \in\{A, B, C\}$ to represent
$$
x_{i j}=\left\{\begin{array}{ll}
1 & \text { employee } i \text { is on team } j \\
0 & \text { otherwise }
\end{array}\right.
$$
Suppose we are writing an integer program, and we have already defined the constraints which ensure that each $x_{i j}$ is a binary variable.

For each of the following conditions, give constraints that correctly formulate it. You may use additional variables. You need to explain why your constrains work.
At least 2 of these 3 conditions hold:

  • Team $A$ has at least 5 years of experience.
  • Team $B$ has at most 250000 in combined annual salary.
  • Teams $B$ and $C$ have the same number of employees.

Question Image

I am working on this optimization problem and have been stuck trying to define and apply binary variables to this question.

I understand what the question is asking and can formulate each constraint individually but I do not know how to formulate the linear constraints such that "at least 2 of the 3 conditions are fulfilled".

My thought was to introduce 3 binary variables for the 3 conditions, say y1, y2, y3, and have them take on the value 1 if the condition is satisfied and 0 otherwise. I do not know how to proceed from here.

Best Answer

With these three binary variables, impose the constraint $y_1+y_2+y_3\ge 2$, together with (linear) big-M constraints that enforce $$y_k =1\implies \text{condition $k$ is satisfied}.$$ Before attempting the big-M constraints, you should model each condition $k$ on its own with a linear constraint that does not involve $y$. For the first condition, $$\sum_{i=1}^7 \alpha_i x_{i,A} \ge 5,$$ rewrite as $$5 - \sum_{i=1}^7 \alpha_i x_{i,A} \le 0,$$ and then the corresponding big-M constraint is $$5 - \sum_{i=1}^7 \alpha_i x_{i,A} \le 5(1-y_1),$$ which you could rewrite as $$\sum_{i=1}^7 \alpha_i x_{i,A} \ge 5 y_1.$$ If $y_1=1$, the constraint enforces the desired condition to be satisfied. If $y_1=0$, the constraint is redundant.

Here, the value of big-M is $5$. More generally, the constraint $$f(x) \le M(1-y),$$ where $M$ is a (small) upper bound on $f(x)$, enforces the rule: if $y=1$ then $f(x) \le 0$.

The second condition is similar. For the third condition, rewrite the equality as two $\le 0$ inequalities and apply big-M to each one separately.

Related Question