mip - mapping of equality to boolean variable

Question

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.

Answer 1

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)

Answer 2

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

Answer 3

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