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,
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
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
Post is closed for comments.
Comments
4 comments