Timeline for Is there any mathematical technique to find the exact solution of a QUBO problem?
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18 at 17:26 | vote | accept | SimoneGasperini | ||
| Jul 18 at 17:26 | comment | added | SimoneGasperini | Ok yes, I've already used the Gurobi solver for integer quadratic programming. Thank you again! | |
| Jul 18 at 16:43 | history | edited | MonteNero | CC BY-SA 4.0 |
added 383 characters in body
|
| Jul 18 at 16:32 | history | edited | MonteNero | CC BY-SA 4.0 |
added 11 characters in body
|
| Jul 18 at 16:31 | comment | added | MonteNero | @SimoneGasperini Simplex and its more advanced variants for quadratic problems combined with branch and bound (BB) or other methods for discretizing variables are considered to be "exact" if the BB method is exhaustive. In other words, you can be sure that the solution you got is proveably optimal. There are many advanced methods and solid theory for quad problems, just start looking into Integer programming, quadratic programming etc. | |
| Jul 18 at 10:27 | comment | added | SimoneGasperini | That's why I thought simply taking the smallest eigenvalue of the diagonal Hamiltonian $H$ (and not the QUBO matrix $Q$, sorry again) could be a good idea. However, it's now clear that the diagonal of $H$ is just enumerating all the possible $\vec{x}_i^T Q \vec{x}_i$ so I guess there is no smarter approach than simply try all the $2^n$ configurations | |
| Jul 18 at 10:15 | comment | added | SimoneGasperini | @MonteNero, thank you very much for the clear answer! I apologize for the confusion about the concept of analytical solution in math, by that I was actually meaning exact solution. So, what I'm interested in is not an heuristic classical solver but instead an approach to find the exact QUBO solution in a reasonable amount of time in practice (for small-size problems) | |
| Jul 18 at 6:12 | comment | added | MonteNero | @MartinVesely, TY. It took me awhile. | |
| Jul 18 at 6:06 | comment | added | Martin Vesely | Very well written! +1 | |
| Jul 18 at 3:58 | history | edited | MonteNero | CC BY-SA 4.0 |
added 190 characters in body
|
| Jul 18 at 3:48 | history | edited | MonteNero | CC BY-SA 4.0 |
added 563 characters in body
|
| Jul 18 at 3:38 | history | edited | MonteNero | CC BY-SA 4.0 |
[Edit removed during grace period]
|
| Jul 18 at 3:27 | history | edited | MonteNero | CC BY-SA 4.0 |
edited body
|
| Jul 18 at 3:21 | history | edited | MonteNero | CC BY-SA 4.0 |
added 1 character in body
|
| Jul 18 at 3:11 | history | edited | MonteNero | CC BY-SA 4.0 |
added 1 character in body
|
| Jul 18 at 3:00 | history | edited | MonteNero | CC BY-SA 4.0 |
added 1 character in body
|
| Jul 18 at 2:54 | history | edited | MonteNero | CC BY-SA 4.0 |
added 11 characters in body
|
| Jul 18 at 2:46 | history | edited | MonteNero | CC BY-SA 4.0 |
deleted 20 characters in body
|
| Jul 18 at 2:38 | history | edited | MonteNero | CC BY-SA 4.0 |
added 429 characters in body
|
| Jul 18 at 2:32 | history | edited | MonteNero | CC BY-SA 4.0 |
added 429 characters in body
|
| Jul 18 at 2:26 | history | edited | MonteNero | CC BY-SA 4.0 |
added 429 characters in body
|
| Jul 18 at 2:15 | history | answered | MonteNero | CC BY-SA 4.0 |