Need some clarification on the Big M utilization for binary variables to turn constraints on or off
Answered
Z = model.addVars(j, vtype=GRB.BINARY, name="Z") #indicator variable
X = model.addVars(j, i, vtype=GRB.BINARY, name="X")
#The above Z[j] indicator variable has been modelled as constraints like this:
# where Zj is an indicator variable, Z j = {1 if ∑ i∈I X ji≥1, 0 otherwise .
model.addConstr(sum(X[j,i] for i in I) >= 1 - BigM*(1-Z[j]) )
model.addConstr(sum(X[j,i] for i in I) <= 1 - 1e-2 + BigM*Z[j] )
I have been reading literature on BigM but still i can't understand how these constraints were modelled like this. Please help me understand the logic behind 1 - BigM*(1-Z[j]) and 1 - BigM*(1-Z[j]).
Best regards,
-
-
Gurobi Staff
Hi Muhammad,
For better understanding these constraints, it may be helpful to try assigning an appropriate numerical value.
Since \(X_{ij}\) is binary, \(\sum_{i \in I}X_{ij}\) can only take the state \(\sum_{i \in I}X_{ij} \geq 1\) or \(\sum_{i \in I}X_{ij} = 0\). First, consider what happens when actually takes such a condition. For \(\sum_{i \in I}X_{ij} \geq 1\), assigning 10 to \(\sum_{i \in I}X_{ij} \), then each constraints will be:
\[\begin{align*}10 \geq& 1-\text{BigM}(1-Z_{j}) \\10 \leq& 1 - 0.01+\text{BigM}Z_{j} \end{align*}\]
The first constraint is always satisfied and can be ignored. To satisfy the second constraint, \(Z_{j}\) must be 1.For \(\sum_{i \in I}X_{ij} =0\), assigning 0 to \(\sum_{i \in I}X_{ij} \), then each constraints will be:
\[\begin{align*} 0 \geq& 1-\text{BigM}(1-Z_{j}) \\0 \leq& 1 - 0.01+\text{BigM}Z_{j}\end{align*}\]
The second constraint is always satisfied and can be ignored. To satisfy the first constraint, \(Z_{j}\) must be 0.Best,
Ryuta0 -
-
Hi Ryuta Tamura,
Thank you for the response. I am interested in understanding how these two constraints were derived. I have reading articles about it but could not crack it so far.0 -
-
-
Hi,
The bigM constraint itself is a well-known method that has been used for a long time and is mentioned in some books like this: "Model Building in Mathematical Programming" by H. Paul Williams.
Best,
Ryuta0 -
Please sign in to leave a comment.
Comments
3 comments