# gurobi bigM constraint vs. epsilon

I am new to mathematical programming and I am trying to implement case specific constrains in Gurobi with Python.

I am wondering about how I can implement my constraints in the fastest or most common way.

There are three variables: $$w_i,w_j \in \mathbb{N}, y_\text{i,j} \in \{0,1\}$$ The indices $$i$$ and $$j$$ referes to fiction tasks since this model takes part of a task scheduling problem. Variable $$w$$ is a weight of the task and $$y$$ shows if task $$i$$ precedes $$j$$. So there are some other constraints to provide some preceding rules.

I need to implement different constraints (let's say $$C_1, C_2, C_3$$) depending to those variables:
$$1: (w_i > w_j) \land (y_\text{i,j} \lor y_\text{j,i}) \rightarrow C_1 \\ 2: (w_i = w_j) \land (y_\text{i,j} \lor y_\text{j,i}) \rightarrow C_2 \\ 3: (w_i < w_j) \land (y_\text{i,j} \lor y_\text{j,i}) \rightarrow C_3$$

To implement this constraint I need introduce new binary variables to the model (let's say $$a_1,a_2,a_3$$) wich are only equal $$1$$, when the refered case is true. Since Gurobi does not implement strict less or greater operators, I need to model a bigM constraints for the variables $$a$$.

$$w_i \ge w_j + \epsilon - M(1-a_1) \\ w_i \le w_j + M \times a_1 \\ a_1 \in {0,1} \\ \epsilon << w_i \tag{1}$$

Since there is a constraint that says, that either $$y_\text{i,j}$$ or $$y_\text{j,i}$$, but not both, are equal 1, I plan to implement a constraint for each case with a new binary variable $$b$$ to represent the logical condition: $$b_1 = a_1 \times (y_\text{i,j} + y_\text{j,i})$$

Finally, I am able to implement each case with an indicator constraint like $$b_x \rightarrow C_x; x\in {1,2,3}$$

At first, I am wondering if the second equation of EQ:1 can also expressed with epsilon instead of M as $$w_i \le (w_j - \epsilon) \times a_1$$.

What is the difference?

Second, Is this the correct way to implement a problem like this or is there a better way?

Changing the second inequality in (1) as proposed would mean that $$w_i \notin (w_j - \epsilon, w_j + \epsilon).$$ It would shrink the feasible region in a way that might be detrimental to the solution of the problem.

To get the split you want (into three cases), you could employ three binary variables $$z_1,z_2,z_3$$ together with the following constraints: $$w_i \ge w_j + \epsilon - M(z_2 + z_3)$$ $$w_j - Mz_2 \le w_i \le w_j + Mz_2$$ $$w_i \le w_j - \epsilon +M(z_1 + z_2)$$ $$z_1 + z_2 + z_3 = 1.$$

The last equation can be used to eliminate one of the binary variables. (I would leave it to the presolver to decide whether to do that.) The three $$z$$ variables correspond to your cases 1, 2 and 3.

• Stronger to replace the first three constraints with: $$\epsilon z_1+0z_2-Mz_3\le w_i-w_j \le M z_1+0z_2-\epsilon z_3$$ Jun 15, 2022 at 16:20
• Since gurobi does not support constraint modeling with multiple operators, I need to split those constraints. Is this correct?
– Mike
Jun 16, 2022 at 10:56
• I showed the $0$ coefficient of $z_2$ for completeness, but $z_2$ is still needed in the equality constraint. You can eliminate any one of $z_i$ by replacing it with $1-z_j-z_k$. For example, you can replace $z_2$ with $1-z_1-z_3$, but you would still need $z_1+z_3 \le 1$. You can think of $z_2$ as a slack variable for the equality constraint. Jun 16, 2022 at 13:02
• @Mike Yes, you would split those constraints.
– prubin
Jun 16, 2022 at 15:17
• @A.Omidi You need additional variables and constraints. Let's say $s_{i,j,1}, s_{i,j,2}, s_{i,j,3}$ are indicators for conditions $C_1, C_2, C_3.$ You want $s_{i,j,1} = z_{i,j,1} \land (y_{i,j}\lor y_{j,i}).$ If $y_{i,j}$ and $y_{j,i}$ are mutually exclusive, you can get by with three constraints: $s_{i,j,1} \le z_{i,j,1},$ $s_{i,j,1} \le y_{i,j} + y_{j,i},$ and $s_{i,j,1}\ge z_{i,j,1} +y_{i,j} + y_{j,i} -1.$ If they are not mutually exclusive, it gets more complicated.
– prubin
Jun 18, 2022 at 16:38