<p>The <a href="http://biqmac.uni-klu.ac.at/biqmaclib.html" rel="nofollow">Biq Mac</a> library provides a collection of instances four your problem. </p>

CC BY-SA 2.5
2011-02-01T14:26:06.950Z
(!) The approximation and heuristic methods works in the problem space, and not in the quadratic monomial space, that means they will always outperform. I read it as there is no practical application for exact algorithm, that is slower then approximated one. (!!) Therefore exact algorithm is interesting only when there is a proof it is exact, then I do not see how to communicate the observation :(.
mkatkov
CC BY-SA 2.5
2011-01-31T21:42:49.927Z
2011-01-31T21:42:49.927Z
Marcus Ritt
<p>I have an algorithm that on all examples I was running finds an  arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary quadratic program is NP-complete, and I cannot prove theoretically, that the algorithm always finds the right solution (it always does in practice). The memory requirement for the algorithm is in current implementation $ n^8 $, where n is the dimension of the problem, it can be reduced to $ n^4 $ leading to possibility to solve the problem in about 50 dimensions, although running time is large - the algorithm have to solve the semi-definite program in $ n^4 $ dimension.</p>

<p>Question: <br> Is there any practical application this algorithm can be used? <br>What benchmarks tests should be performed to demonstrate practical usefulness of the algorithm?</p>

<p>I'm not sure I'm allowed to post the link, so you can find details of the algorithm, and its python implementation though the link in my profile, or  here, if link works.</p>

<p>PS. I apologize if this is off topic question, I got algorithm by a complete chance, and have no idea where and how to communicate it. </p>

<p>PPS. I know it goes completely against the public opinion, but this is a testable objective, so give it a chance to survive, at least to the moment when it finds counterexample, or can be used as a practical application without a proof.</p>

CC BY-SA 2.5
2011-01-31T18:34:06.260Z
Silly comment: I have learned that BQP does not always mean [bounded-error quantum polynomial time](http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bqp).
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-31T18:37:42.907Z
BQP is removed.
mkatkov
CC BY-SA 2.5
2011-01-31T20:18:14.523Z
Oh.  I did not mean “Do not use the word BQP for other meanings than what I know!”
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-31T20:27:44.707Z
I was kicked to death by the experts, so I prefer to follow any expert's advise, that does not change meaning, to get something useful.
mkatkov
CC BY-SA 2.5
2011-01-31T23:14:16.683Z
You could outline your idea here to give people an idea of what you are talking about. Also, your statement "if it cannot be proved it can be used" (from your blog) disturbs me.
Raphael
CC BY-SA 2.5
2011-02-01T02:20:09.470Z
In practice it was always possible to find the optimal point $ x^* $ (the fact which is also hard to prove, and is probably due to round-off errors), so it is possible to compare the output of the algorithm, with the actual value. Since Parrilo/Shor algorithm provides lower bound the present algorithm output is either close to the actual value, or much below it. This way it is possible to check whether it is correct solution, or it is a counterexample. Therefore, algorithm can be used until it finds counterexample, if any.
mkatkov
<ds.algorithms><advice-request><integer-programming><semidefinite-programming>
Applications and benchmarks for binary quadratic program algorithms
mkatkov
# Applications and benchmarks for binary quadratic program algorithms

(Asked by: username_0 on 2011-01-31)

I have an algorithm that on all examples I was running finds an arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary quadratic program is NP-complete, and I cannot prove theoretically, that the algorithm always finds the right solution (it always does in practice). The memory requirement for the algorithm is in current implementation $ n^8 $, where n is the dimension of the problem, it can be reduced to $ n^4 $ leading to possibility to solve the problem in about 50 dimensions, although running time is large - the algorithm have to solve the semi-definite program in $ n^4 $ dimension.

Question:   
 Is there any practical application this algorithm can be used?   
What benchmarks tests should be performed to demonstrate practical usefulness of the algorithm?

I'm not sure I'm allowed to post the link, so you can find details of the algorithm, and its python implementation though the link in my profile, or here, if link works.

PS. I apologize if this is off topic question, I got algorithm by a complete chance, and have no idea where and how to communicate it.

PPS. I know it goes completely against the public opinion, but this is a testable objective, so give it a chance to survive, at least to the moment when it finds counterexample, or can be used as a practical application without a proof.

**Tags:** ds.algorithms, advice-request, integer-programming, semidefinite-programming

> **Comments:**
> **username_1**: Silly comment: I have learned that BQP does not always mean [bounded-error quantum polynomial time](http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bqp).  
> **username_0**: BQP is removed.  
> **username_1**: Oh.  I did not mean “Do not use the word BQP for other meanings than what I know!”  
> **username_0**: I was kicked to death by the experts, so I prefer to follow any expert's advise, that does not change meaning, to get something useful.  
> **username_2**: You could outline your idea here to give people an idea of what you are talking about. Also, your statement "if it cannot be proved it can be used" (from your blog) disturbs me.  
> **username_0**: In practice it was always possible to find the optimal point $ x^* $ (the fact which is also hard to prove, and is probably due to round-off errors), so it is possible to compare the output of the algorithm, with the actual value. Since Parrilo/Shor algorithm provides lower bound the present algorithm output is either close to the actual value, or much below it. This way it is possible to check whether it is correct solution, or it is a counterexample. Therefore, algorithm can be used until it finds counterexample, if any.  

---

## 1 answers

### Answer by username_3 on 2011-01-31. Score: 4 | Accepted answer

The [Biq Mac](http://biqmac.uni-klu.ac.at/biqmaclib.html) library provides a collection of instances four your problem.

> **Comments:**
> **username_0**: (!) The approximation and heuristic methods works in the problem space, and not in the quadratic monomial space, that means they will always outperform. I read it as there is no practical application for exact algorithm, that is slower then approximated one. (!!) Therefore exact algorithm is interesting only when there is a proof it is exact, then I do not see how to communicate the observation :(.  

---

