• 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ł

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?

• 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.