1
$\begingroup$

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.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ i.imgur.com/IZATTiz.jpg This is what I had for the 3 conditions separately. I tried to involve the variable y by multiplying it on the right-hand side and editing each expression to satisfy what I need, but wasn't sure exactly how. $\endgroup$ Commented Jan 20, 2020 at 17:03
  • $\begingroup$ Please use MathJax. $\endgroup$ Commented Jan 20, 2020 at 17:10
  • $\begingroup$ Thank you for showing me an example. I am working on the second condition right now. This is what I have, $$\sum_{i=1}^7 \beta_i x_{i,B} \le 250000y_2$$ so the big-M value would be 250000. However I see that when $y_2$=0, then the constraint would imply that Team B's combined salary would be negative. Also the other constraint, $$\sum_{i=1}^7 \beta_i x_{i,B} \ge 250000(1-y_2)$$ is not redundant and if $y_2$=0 would not satisfy the question. $\endgroup$ Commented Jan 20, 2020 at 17:40
  • $\begingroup$ For the second condition, first rewrite as $\le 0$, and then obtain $M$ as a small upper bound on the LHS. $\endgroup$ Commented Jan 20, 2020 at 17:43
  • $\begingroup$ $$\sum_{i=1}^7 \beta_i x_{i,B} \le 250000$$ $$\sum_{i=1}^7 \beta_i x_{i,B} - 250000 \le 0$$ $$\sum_{i=1}^7 \beta_i x_{i,B} - 250000 \le 250000(1-y_2)$$ $$\sum_{i=1}^7 \beta_i x_{i,B} \le 250000(2-y_2)$$ Is this the correct way to approach condition 2? I see that if $y_2$=0 then the constraint is redundant. $\endgroup$ Commented Jan 20, 2020 at 17:53

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.