3
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
8
  • 1
    $\begingroup$ 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$$ $\endgroup$
    – RobPratt
    Jun 15, 2022 at 16:20
  • $\begingroup$ Since gurobi does not support constraint modeling with multiple operators, I need to split those constraints. Is this correct? $\endgroup$
    – Mike
    Jun 16, 2022 at 10:56
  • 2
    $\begingroup$ 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. $\endgroup$
    – RobPratt
    Jun 16, 2022 at 13:02
  • 1
    $\begingroup$ @Mike Yes, you would split those constraints. $\endgroup$
    – prubin
    Jun 16, 2022 at 15:17
  • 1
    $\begingroup$ @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. $\endgroup$
    – prubin
    Jun 18, 2022 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.