# mip - mapping of equality to boolean variable

I want to create mip model which assign workers to entities. In case neighbour entities use same worker, objective should be increased by 1. A goal is to maximize total number of same workers for neighbour entities.

Since number of combinations can be large, I prefer integer variable to hold index of assigned worker (allowed only one worker per entity) to an entity. It works for me with usage of big M, boolean variable (assignment of concrete worker) is mapped to an index.

I don't how to map equality of indexes for two entities to boolean variable.

For example

• e1.w = 1, e2.w = 1 imply 1
• e1.w = 2, e2.w = 1 imply 0
• e1.w = 2, e2.w = 2 imply 1

Is it possible to model it in mip ? Otherwise I have to for every possible combination of indexes create less or equal equation to trigger equality of workers.

• Is any typo for the second point? If I am not misunderstand, I think it should be e1.w=2, e2.w=1, right? Sep 25 at 15:51
• yes, you are right. Sep 25 at 16:28
• @gregy4, is the problem relevant yet? If No, please accept one of the answers. Otherwise, explain more about the problem you mentioned, specifically, the type of decision variables and the meaning of the one and zero in the RHS. Sep 26 at 9:38

Let $$x_1 = e1.w$$, $$x_2 = e2.w$$, $$M$$ is a big value, $$y$$ is binary variable which represent whether is the same worker be assigned into neighbor entities (0 means the same, 1 means different)

$$|x_1-x_2| ≤ My$$

Above inequality can transfer into the following:

$$x_1 - x_2 ≤ My$$

$$x_2 - x_1 ≤ My$$

Objective function: $$min: y$$

In general, the number of binary variables is (the number of entities - 1)

• This won't work as $0 \leq M y$ doesn't imply anything for $x_1 = x_2$.
– joni
Sep 25 at 17:18
• I cannot get your point. My opinion is that if $x_1=x_2$ implies $y=0$ then means the neighbor is the same, otherwise those are different workers. $y$ means whether entity i and entity i+1 is same or not. Combine the objective function to minimize the binary variables, I think that would work. Could you provide your idea to explain me why that not work? Thanks Sep 25 at 18:52
• I've totally overlooked that you proposed an objective function. Sorry, my bad.
– joni
Sep 25 at 19:15

If I understood correctly, you want to enforce

\begin{align} e_{1,w} = e_{2,w} \implies b_{w} = 1 \quad \text{for all } w, \tag{1} \\ e_{1,w} \neq e_{2,w} \implies b_{w} = 0 \quad \text{for all } w. \tag{2} \end{align}

Note that (2) is equivalent to $$b_w = 1 \implies e_{1,w} = e_{2,w}$$ and thus you'd like to enforce

$$e_{1,w} = e_{2,w} \iff b_{w} = 1 \quad \text{for all } w. \tag{*}$$

Assuming $$0 \leq e_{1,w},e_{2,w} \leq U$$, you can model (*) by introducing two binary variables $$h_{1,w}, h_{2,w}$$ for all $$w$$ and imposing the constraints

\begin{align} -U \cdot h_{w,1} + h_{w,2} &\leq e_{1,w} - e_{2,w} \leq - h_{w,1} + U \cdot h_{w,2} \qquad &\text{for all } w \\ h_{w,1} + h_{w,2} + b_w &= 1 &\qquad \text{for all } w. \end{align}

Define a binary variable (like an edge of a graph where $$V=$$ set of entities $$e$$) $$y_{u,v}$$ where $$y=1$$ if entities $$u,v \in V$$ share the same worker from set of workers $$\{1,2,3....W\}$$, else $$0$$. You can model workers assigned to an entity $$v$$ as integer variable $$w_u$$.
Two more additional binary variables are needed $$y^+, y^-$$

2 set of constraints
$$M(y_{u,v} - 1) - My_{u,v}^- + w_v \le w_u \le w_v + M (1-y_{u,v}) - M y_{u,v}^+$$

$$y_{u,v} + y_{u,v}^+ + y_{u,v}^- = 1 \ \ \forall u,v \in E$$

Obj = $$\sum_{u,v}y_{u,v}$$