Help with MILP formulation.

[JavalVyas2000]

I am trying to formulate a QUBO for a MILP scheduling problem which has 3 equations and an objective function. The model is formulated as

RTN=Model(Gurobi.Optimizer)
@constraint(RTN, Balance[r in R, t in T1],
X[r,t] -
(X[r,t-1]
+ ∑(
μ[i,r,θ] * N[i,t-θ]
+ ν[i,r,θ] * ξ[i,t-θ]
for i in Ir[r], θ in 0:max_tau if θ ≤ tau[i] && t-θ ≥ 1
)
+ Π[r,t])==0
)
@constraint(RTN, ResourceLB[r in R, t in T1],
X[r,t]-Xmin[r]>=0
)
@constraint(RTN, ResourceUB[r in R, t in T1],
Xmax[r]-X[r,t]>=0
)
@constraint(RTN, BatchLB[i in I, t in T1],
ξ[i,t]- ( Vmin[i] * N[i,t])>=0
)
@constraint(RTN, BatchUB[i in I, t in T1],
Vmax[i] * N[i,t]-ξ[i,t]>=0
)
@objective(RTN,
Min,
∑(N[i,t] for i in I, t in T1)
)

Here, N[i,t] is a binary variable, X[r,t] and ξ[i,t] are continous variables, rest all are parameters. I am able to solve this model with gurobi to an objective value of 5 in under a second (which it should be), but when I use the TOQUBO.jl to reformulate it as a QUBO and solve the problem my objective value reached in the range of 1e16 and takes around 300+ seconds.

To convert to QUBO, I implement the model as
RTN=Model(() -> ToQUBO.Optimizer(DWaveNeal.Optimizer))
And then write the above constraints and objective.

Am I missing something? Kindly help me with this implementation.

[pedroripper]

Hi @JavalVyas2000 !

When we convert a general problem to a QUBO, the resulting model might be loosing some of its original information...

When encoding continuous variables, there is no exact solution as with integer ones. So there are probably some error being introduced at this step. Also, your original problem seems quite big, so the final QUBO probably has a large amount of variables and accumulated errors.

However, I believe that the main issue is the penalization of your constraints. Our reformulator might not be calculating the correct penalty for each of your constraints. Also, due to the fact that the variables are not integer, the bounds for the constraints may not be tight enough.

We are currently finishing an update on our code that allows the user to set the penalization value, so it would be possible to "tune" your QUBO model to with the appropriate penalizations.

I will reach out to you as soon as we are finished with the update 🙂

[JavalVyas2000]

Thank you for the update Pedro. Looking forward to the next version. Regards, Javal

…

On Sun, Nov 19, 2023 at 3:19 PM Pedro Ripper ***@***.***> wrote: Hi @JavalVyas2000 <https://github.com/JavalVyas2000> ! When we convert a general problem to a QUBO, the resulting model might be loosing some of its original information... When encoding continuous variables, there is no exact solution as with integer ones. So there are probably some error being introduced at this step. Also, your original problem seems quite big, so the final QUBO probably has a large amount of variables and accumulated errors. However, I believe that the main issue is the penalization of your constraints. Our reformulator might not be calculating the correct penalty for each of your constraints. Also, due to the fact that the variables are not integer, the bounds for the constraints may not be tight enough. We are currently finishing an update on our code that allows the user to set the penalization value, so it would be possible to "tune" your QUBO model to with the appropriate penalizations. I will reach out to you as soon as we are finished with the update 🙂 — Reply to this email directly, view it on GitHub <#80 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ARQAWUWOXZFXF7Q4V63CFJ3YFJSUDAVCNFSM6AAAAAA7NPLDXGVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTQMJXHE3DMMBSGQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>