Skip to main content

Need some clarification on the Big M utilization for binary variables to turn constraints on or off

Answered

Comments

4 comments

  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    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.
  • Ryuta Tamura
    • 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,
    Ryuta 

    0
  • Muhammad Ahsan Farooq Rajput
    • Gurobi-versary
    • First Comment
    • First Question

    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
  • Ryuta Tamura
    • Gurobi Staff

    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,
    Ryuta

    0

Post is closed for comments.