Skip to main content

Facility Location Problem - Standard BIP vs QUBO

Awaiting user input

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.
  • Jaromił Najman
    • Gurobi Staff

    Hi Abishek,

    In your BIP formulation, you don't have any constraints. There is only a linear objective function, thus the model is easy to solve.

    In your QUBO with penalty function, you introduce 2 constraints via penalties. The constraints are enforced because the penalty is bigger if they are not fulfilled.

    The first constraint is in \(\texttt{Penalty1}\) and reads

    \[\begin{align*}
    \sum_{i} \text{ServiceSelect}_{i,j} = 1 \quad \forall j
    \end{align*}\]

    and the constraint hidden in \(\texttt{Penalty2}\) reads

    \[\begin{align*}
    \sum_{i,j} (\text{ServiceSelect}_{i,j}  - \text{ServiceSelect}_{i,j} *\text{FacilitySelect}_{i,j} = 0
    \end{align*}\]

    I don't know about the second QUBO formulation as no details about \(Q\) are given but I assume that something similar is happening.

    Best regards, 
    Jaromił

    0
  • Abhishek Solomon
    • Gurobi-versary
    • Curious
    • Conversationalist

    Thank you Jaromil. I do have constraints in the BIP model, i have just shown the objective function above. The constraints used are:

    for i in facilities:
        for j in customers:
            m.addConstr(ServiceSelect[i,j] <= FacilitySelect[i], 'Constraint1')

    for j in customers:
        m.addConstr(gp.quicksum((ServiceSelect[i,j]) for i in facilities) == 1 , 'Constraint2')

    For the second QUBO formulation, I am manually generating the Q matrix using logically assumed penalties based on research. Once the Q matrix is generated, i do the following:

    Q = np.array(Q)
    x = m.addVars(Q.shape[0], vtype=gp.GRB.BINARY)
    objective = gp.quicksum(x[i] * x[j] * Q[i, j] for i in range(Q.shape[0]) for j in range(Q.shape[0]))

    m.setObjective(objective, gp.GRB.MINIMIZE)

    What I am trying to understand is, are there any specific tuning/tweaking parameters that I need to invoke to solve QUBO models in Gurobi?

    0
  • Jaromił Najman
    • Gurobi Staff

    In your BIP formulation, you have the constraints

    for i in facilities:
        for j in customers:
            m.addConstr(ServiceSelect[i,j] <= FacilitySelect[i], 'Constraint1')

    I don't see how these constraints translate into the penalty term

    Penalty2 = p*(gp.quicksum(ServiceSelect[i,j] - ServiceSelect[i,j]*FacilitySelect[i] for i in facilities for j in customers))

    Where does the bilinear term ServiceSelect[i,j]*FacilitySelect[i] come from?

    Could you share the logs for the 3 runs?

    What I am trying to understand is, are there any specific tuning/tweaking parameters that I need to invoke to solve QUBO models in Gurobi?

    You should definitely use the latest Gurobi version if you are solving QUBOs. You could try experimenting with the PreQLinearize parameter.

    0

Post is closed for comments.