QUBO solver limitations
AnsweredDear Sirs, I have a problem formulated as a QUBO and want to use GUROBI to try to optimize it.
I am completely new to GUROBI, so I want to ask you about the limitations of the solver as the size of the problem and maybe some "best practices" on how to use/tune solver for that type of problems.
Note, for the toy problem I have about 20k variables while the actual size can be up to 1,000,000 variables - so available memory is the only limitation?
Because I understand that even 100,000 x 100,000 matrix of float64 values in NumPy will consume 80,000,000,000 bytes of memory, which is approx 74.51 gigabytes.. and it's a rough estimate..
Appreciate for links and examples.
-
-
Gurobi Staff
Hi,
A QUBO is essentially an instance of binary quadratic programming and you can in theory solve an optimization model with Gurobi as long as the sum of the number of variables and constraints is less than ~2 billions. Of course, this is just in theory and the actual size of a model that can be solved by Gurobi can be much smaller depending on the model structure.
You are correct that as the size of the model increases, the machine should have enough memory to store the model and carry the optimization.
Is your QUBO fully connected or sparse? Solving a fully connected QUBO with 1 million variables would be very challenging especially if the goal is to prove optimality.
You can experiment with parameters below when solving a QUBO:
- NoRelHeurTime to force running the no-relaxation heuristic algorithm before solving the root relaxation with the aim of reaching a high-quality solution as quickly as possible.
- PreQLinearize=1|2 to force the linearization of quadratic terms in the objective function and solve the problem as an instance of binary linear programming
If your problem is an instance of constrained optimization problem where the constraints are penalized in the objective function to transfer the model into a QUBO, we highly recommend using Gurobi to solve the constrained problem directly.
Best regards,
Maliheh
0 -
-
If your problem is an instance of constrained optimization problem where the constraints are penalized in the objective function to transfer the model into a QUBO, we highly recommend using Gurobi to solve the constrained problem directly.
What do you mean by "solve the constrained problem directly"? - without PreQLinearize?
0 -
-
-
What do you mean by "solve the constrained problem directly"? - without PreQLinearize?
The optimization problems are not naturally QUBOs because they are usually constrained. To reformulate the problem as a QUBO, the constraints are penalized in the objective function. My point was that instead of reformulating the problem as a QUBO, solve the problem as an instance of constrained optimization with Gurobi. For example, consider the constrained optimization problem as \(\min\{c^Tx| Ax = b\}\). To solve this problem as a QUBO, you need to reformulate it as \(\min\{c^Tx + P(Ax-b)^2\}\) with \(P\) being penalty multipliers. My point was to solve the problem as \(\min\{c^Tx| Ax = b\}\) with Gurobi.
Best regards,Maliheh
0 -
Please sign in to leave a comment.
Comments
3 comments