| Name | quboassist JSON |
| Version |
0.0.1
JSON |
| download |
| home_page | None |
| Summary | Generate QUBO which can be input to dwave-neal simulated annealing solver and reconstruct the solution of the original problem. |
| upload_time | 2024-09-29 13:05:42 |
| maintainer | None |
| docs_url | None |
| author | None |
| requires_python | >=3.7 |
| license | MIT License Copyright (c) 2024 enomotokan Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
| keywords |
qubo
simulated annealing
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
```
```
# quboassist
This is a package to generate QUBO which can be input to dwave-neal simulated annealing solver and reconstruct the solution of the original problem from the output.
## What problems is it applicable to?
This package converts the problem below into QUBO form which can be input directly to dwave-neal package:
$$
{\rm minimize}\ \ \ f(x) =x^t Ax\\
$$
$$
s.t. \ \ \ \forall i, a_i \leq x_i\leq b_i,x_i\in\mathbb Z
$$
$$
\forall j, \sum_ kc_{jk} x_k \geq d_j\ \ (c_{jk}, d_j \in \mathbb Z)
$$
where $A$ is a symmetric real matrix. I.e. problems where the objective function is quadratic, all variables are bounded and integer, all constraints are linear and their all coefficients are integer.
## How to use
First, import the all classes of quboassist.
```
from quboassist import *
import neal
```
There are three classes: `Variable`, `Formula`, `Problem`. Using `Variable` class, we can define variables.
```
x = [Variable("x{}".format(i), 2, 5) for i in range(10)]
```
The fist component of input is the name of the variable. The second is the minimum value and the last is the maximum value, so this variable "x" takes $2,3,4,5$. If you want to change the passible values of the variable, you can do the following.
```
x[4].change_max(4)
x[5].change_min(-2)
```
`Formula` is a class whose instance is generated automatically when variables are operated. For example,
```
f = - x[0]**2 - 3 * x[1]
g = x[0] > x[1]
```
then `f`, `g` are instances of `Formula`. Finally, we can define a problem using `Problem`.
```
P = Problem()
P.add_objective(f)
P.add_constraint(10, g)
```
where the first input of `add_constraint` method is the weight of the constraint. Finally, we can get QUBO by `compile` method.
```
P.compile()
sampler = neal.SimulatedAnnealingSampler()
result = sampler.sample_qubo(P.qubo).first.sample
solution = P.solution(result)
print(solution)
```
The solution is almost always below .
```
({'x0': 5, 'x1': 4}, [True])
```
The second component means whether each solution satisfies each constraint conditions. In the above case, because $5 > 4$, the return is true. Note that heuristic algorithms do not necessarily return an exact solution, so we always need to pay attention to the second component.
In general, increasing the weight $w_i$ tends to make it easier to satisfy the condition, but the objective function becomes relatively smaller. Therefore we propose to use a library called optuna to tune these hyperparameters $w_i$.
A sample code is showed below.
```
import neal
import quboassist
import optuna
import numpy as np
from copy import copy
x = [quboassist.Variable("x{}".format(i), 0, 3) for i in range(10)]
best_solution = []
best_val = np.inf
def objective(trial):
P = quboassist.Problem()
f = - x[0]**2 - x[1]
P.add_objective(f)
w = [trial.suggest_float("w{}".format(i), 0, 5) for i in range(2)]
g = x[0] > x[1]
P.add_constraint(w[0], g)
h = x[0] + x[1] == x[2]
P.add_constraint(w[1], h)
P.compile()
sampler = neal.SimulatedAnnealingSampler()
result = sampler.sample_qubo(P.qubo).first
solution = P.solution(result.sample)
obj = w[0] + w[1] + 10 * sum(np.logical_not(solution[1]))
val = result.energy
# Note that result.energy and the value of objective function may differ by a constant which appears when expanding the product of variables!
global best_solution, best_val
if val < best_val:
best_val = val
best_solution = copy(solution)
return obj
study = optuna.create_study(direction="minimize")
study.optimize(objective, n_trials=15)
print(best_solution)
```
## What kind of technique is used?
The core is as below. We leave it to the reader to consider how to use this to represent any bounded integer variable as a linear combination of a constant and a binary variable, and to convert an inequality into an equality.
Algorithm
------
Input: $n$
Output: $A(n)$
Define $A_0(n) \leftarrow 2^{\lfloor \log_2 (n + 1) \rfloor - 1}, n_1 \leftarrow n - A_0(n), k \leftarrow 0$
while $n_{k+1} \neq 0$ do
$A_{k + 1}(n) \leftarrow 2^{\lfloor \log_2 (n_{k + 1} + 1) \rfloor - 1}$
$k \leftarrow k + 1$
$n_{k + 1}\leftarrow n_k - A_k(n)$
end while
------
*Lemma*
For all $n \in \mathbb N$, the sequence $A(n)$ is finite and the length is at most
$$
2\lfloor\log_2(n +1)\rfloor.
$$
Moreover, a function $f: [0,1]^k \rightarrow \mathbb N$ defined as:
$$
f(x_1,x_2,...,x_k):= \sum_{i =1}^k A_i(n) x_i
$$
takes the all numbers $0,...,n$ and no other values.
*Proof.*
Since $A_0(n)$ is the only power of two which satisfies $4A_0(n)> n+1 \geq 2 A_0(n)$,
$$
n - A_0(n) \geq A_0(n)-1
$$
i.e.
$$
A_1(n)=2^{\lfloor\log_2(n_1 +1)\rfloor-1}\geq \frac{1}{2}A_0(n)
$$
holds if $n_1 \neq 0$. Therefore if $A_0(n) \geq 2$, then $A_1(n) = A_0(n)$ or $A_1(n) =\frac{1}{2} A_0(n)$. Moreover, in the case that the first two numbers of $A(n)$ is same,
$$
n_2=n-2A_1(n)<2A_1(n)-1
$$
i.e.
$$
A_2(n)=2^{\lfloor\log_2(n_2 +1)\rfloor-1}<A_1(n).
$$
Hence the same number appears at most two times in $A(n)$ and the exponent $\lfloor\log_2(n_k +1)\rfloor-1$ is monotonically non-increasing, thus the length of $A(n)$ is at most
$$
2\lfloor\log_2(n +1)\rfloor,
$$
moreover by the same reason, we also conclude the sequence $A(n)$ includes all powers of two
less than or equal to
$$
2^{\lfloor\log_2(n +1)\rfloor-1}(= A_0(n)).
$$
Therefore, numbers $0,...,2A_0(n)-1$ can be expressed as
$$
\sum_{i=1}^kA_i(n)x_i
$$
and numbers $n-2A_0(n),...,n$ can be expressed as
$$
n-\sum_{i=1}^kA_i(n)y_i=\sum_{i=1}^kA_i(n)(1-y_i).
$$
Since
$$
n-2A_0(n)< 2A_0(n) -1,
$$
finally all numbers $0,...,n$ can be expressed as
$$
\sum_{i=1}^kA_i(n)x_i.
$$
<div style="text-align: right;">
□
</div>
Raw data
{
"_id": null,
"home_page": null,
"name": "quboassist",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": null,
"keywords": "QUBO, Simulated annealing",
"author": null,
"author_email": "Enomoto Kan <enomotokan@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/bd/ec/1524199e7e9f8cec49fd2c0468b95d0087bd3d887231de7a314eff2113a6/quboassist-0.0.1.tar.gz",
"platform": null,
"description": "```\r\n\r\n```\r\n\r\n# quboassist\r\n\r\nThis is a package to generate QUBO which can be input to dwave-neal simulated annealing solver and reconstruct the solution of the original problem from the output.\r\n\r\n## What problems is it applicable to?\r\n\r\nThis package converts the problem below into QUBO form which can be input directly to dwave-neal package:\r\n\r\n\r\n$$\r\n{\\rm minimize}\\ \\ \\ f(x) =x^t Ax\\\\\r\n$$\r\n\r\n$$\r\ns.t. \\ \\ \\ \\forall i, a_i \\leq x_i\\leq b_i,x_i\\in\\mathbb Z\r\n$$\r\n\r\n$$\r\n\\forall j, \\sum_ kc_{jk} x_k \\geq d_j\\ \\ (c_{jk}, d_j \\in \\mathbb Z)\r\n$$\r\n\r\n\r\n\r\nwhere $A$ is a symmetric real matrix. I.e. problems where the objective function is quadratic, all variables are bounded and integer, all constraints are linear and their all coefficients are integer.\r\n\r\n## How to use\r\n\r\nFirst, import the all classes of quboassist.\r\n\r\n```\r\nfrom quboassist import *\r\nimport neal\r\n```\r\n\r\nThere are three classes: `Variable`, `Formula`, `Problem`. Using `Variable` class, we can define variables.\r\n\r\n```\r\nx = [Variable(\"x{}\".format(i), 2, 5) for i in range(10)]\r\n```\r\n\r\nThe fist component of input is the name of the variable. The second is the minimum value and the last is the maximum value, so this variable \"x\" takes $2,3,4,5$\u200b. If you want to change the passible values of the variable, you can do the following.\r\n\r\n```\r\nx[4].change_max(4)\r\nx[5].change_min(-2)\r\n```\r\n\r\n`Formula` is a class whose instance is generated automatically when variables are operated. For example, \r\n\r\n```\r\nf = - x[0]**2 - 3 * x[1]\r\ng = x[0] > x[1]\r\n```\r\n\r\nthen `f`, `g` are instances of `Formula`. Finally, we can define a problem using `Problem`.\r\n\r\n```\r\nP = Problem() \r\nP.add_objective(f)\r\nP.add_constraint(10, g)\r\n```\r\n\r\nwhere the first input of `add_constraint` method is the weight of the constraint. Finally, we can get QUBO by `compile` method.\r\n\r\n```\r\nP.compile()\r\n\r\nsampler = neal.SimulatedAnnealingSampler()\r\nresult = sampler.sample_qubo(P.qubo).first.sample\r\nsolution = P.solution(result)\r\nprint(solution)\r\n```\r\n\r\nThe solution is almost always below .\r\n\r\n```\r\n({'x0': 5, 'x1': 4}, [True])\r\n```\r\n\r\nThe second component means whether each solution satisfies each constraint conditions. In the above case, because $5 > 4$, the return is true. Note that heuristic algorithms do not necessarily return an exact solution, so we always need to pay attention to the second component. \r\n\r\nIn general, increasing the weight $w_i$ tends to make it easier to satisfy the condition, but the objective function becomes relatively smaller. Therefore we propose to use a library called optuna to tune these hyperparameters $w_i$.\r\n\r\nA sample code is showed below.\r\n\r\n```\r\nimport neal\r\nimport quboassist\r\nimport optuna\r\nimport numpy as np\r\nfrom copy import copy\r\n\r\nx = [quboassist.Variable(\"x{}\".format(i), 0, 3) for i in range(10)]\r\n\r\nbest_solution = []\r\nbest_val = np.inf\r\n\r\ndef objective(trial):\r\n\r\n P = quboassist.Problem()\r\n\r\n f = - x[0]**2 - x[1]\r\n P.add_objective(f)\r\n\r\n w = [trial.suggest_float(\"w{}\".format(i), 0, 5) for i in range(2)]\r\n\r\n g = x[0] > x[1]\r\n P.add_constraint(w[0], g)\r\n\r\n h = x[0] + x[1] == x[2]\r\n P.add_constraint(w[1], h)\r\n\r\n P.compile()\r\n\r\n sampler = neal.SimulatedAnnealingSampler()\r\n result = sampler.sample_qubo(P.qubo).first\r\n solution = P.solution(result.sample)\r\n \r\n obj = w[0] + w[1] + 10 * sum(np.logical_not(solution[1]))\r\n val = result.energy\r\n \r\n # Note that result.energy and the value of objective function may differ by a constant which appears when expanding the product of variables!\r\n\r\n global best_solution, best_val\r\n \r\n if val < best_val:\r\n best_val = val\r\n best_solution = copy(solution)\r\n \r\n return obj\r\n\r\nstudy = optuna.create_study(direction=\"minimize\")\r\nstudy.optimize(objective, n_trials=15)\r\n\r\nprint(best_solution)\r\n```\r\n\r\n\r\n\r\n## What kind of technique is used?\r\n\r\n\r\n\r\nThe core is as below. We leave it to the reader to consider how to use this to represent any bounded integer variable as a linear combination of a constant and a binary variable, and to convert an inequality into an equality.\r\n\r\n\r\n\r\nAlgorithm\r\n\r\n------\r\n\r\nInput: $n$\r\n\r\nOutput: $A(n)$\r\n\r\n\u200b Define $A_0(n) \\leftarrow 2^{\\lfloor \\log_2 (n + 1) \\rfloor - 1}, n_1 \\leftarrow n - A_0(n), k \\leftarrow 0$\r\n\r\n\u200b while $n_{k+1} \\neq 0$ do\r\n\r\n\u200b $A_{k + 1}(n) \\leftarrow 2^{\\lfloor \\log_2 (n_{k + 1} + 1) \\rfloor - 1}$\t\r\n\r\n\u200b $k \\leftarrow k + 1$\r\n\r\n\u200b $n_{k + 1}\\leftarrow n_k - A_k(n)$\r\n\r\n\u200b end while\r\n\r\n------\r\n\r\n\r\n\r\n*Lemma*\r\n\r\nFor all $n \\in \\mathbb N$, the sequence $A(n)$\u200b is finite and the length is at most\r\n\r\n\r\n$$\r\n2\\lfloor\\log_2(n +1)\\rfloor.\r\n$$\r\n \r\n\r\nMoreover, a function $f: [0,1]^k \\rightarrow \\mathbb N$ defined as:\r\n\r\n\r\n$$\r\nf(x_1,x_2,...,x_k):= \\sum_{i =1}^k A_i(n) x_i\r\n$$\r\n\r\n\r\ntakes the all numbers $0,...,n$ and no other values.\r\n\r\n\r\n\r\n*Proof.*\r\n\r\nSince $A_0(n)$ is the only power of two which satisfies $4A_0(n)> n+1 \\geq 2 A_0(n)$, \r\n\r\n\r\n$$\r\nn - A_0(n) \\geq A_0(n)-1\r\n$$\r\n\r\n\r\ni.e.\r\n\r\n\r\n$$\r\nA_1(n)=2^{\\lfloor\\log_2(n_1 +1)\\rfloor-1}\\geq \\frac{1}{2}A_0(n)\r\n$$\r\n\r\n\r\nholds if $n_1 \\neq 0$. Therefore if $A_0(n) \\geq 2$, then $A_1(n) = A_0(n)$ or $A_1(n) =\\frac{1}{2} A_0(n)$. Moreover, in the case that the first two numbers of $A(n)$\u200b is same, \r\n\r\n\r\n$$\r\nn_2=n-2A_1(n)<2A_1(n)-1\r\n$$\r\n\r\n\r\ni.e.\r\n\r\n\r\n$$\r\nA_2(n)=2^{\\lfloor\\log_2(n_2 +1)\\rfloor-1}<A_1(n).\r\n$$\r\n\r\n\r\nHence the same number appears at most two times in $A(n)$ and the exponent $\\lfloor\\log_2(n_k +1)\\rfloor-1$ is monotonically non-increasing, thus the length of $A(n)$ is at most\r\n\r\n\r\n$$\r\n2\\lfloor\\log_2(n +1)\\rfloor,\r\n$$\r\n\r\n\r\nmoreover by the same reason, we also conclude the sequence $A(n)$ includes all powers of two\r\nless than or equal to\r\n\r\n\r\n$$\r\n2^{\\lfloor\\log_2(n +1)\\rfloor-1}(= A_0(n)).\r\n$$\r\n\r\n\r\nTherefore, numbers $0,...,2A_0(n)-1$\u200b can be expressed as\r\n\r\n\r\n$$\r\n \\sum_{i=1}^kA_i(n)x_i\r\n$$\r\n\r\n\r\nand numbers $n-2A_0(n),...,n$\u200b can be expressed as\r\n\r\n\r\n$$\r\nn-\\sum_{i=1}^kA_i(n)y_i=\\sum_{i=1}^kA_i(n)(1-y_i).\r\n$$\r\n \r\n\r\nSince\r\n\r\n\r\n$$\r\nn-2A_0(n)< 2A_0(n) -1,\r\n$$\r\n\r\n\r\nfinally all numbers $0,...,n$\u200b\u200b can be expressed as\r\n\r\n\r\n$$\r\n\\sum_{i=1}^kA_i(n)x_i.\r\n$$\r\n\r\n<div style=\"text-align: right;\">\r\n\u25a1\r\n</div>\r\n\r\n",
"bugtrack_url": null,
"license": "MIT License Copyright (c) 2024 enomotokan Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the \"Software\"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. ",
"summary": "Generate QUBO which can be input to dwave-neal simulated annealing solver and reconstruct the solution of the original problem.",
"version": "0.0.1",
"project_urls": {
"Homepage": "https://github.com/enomotokan/quboassist"
},
"split_keywords": [
"qubo",
" simulated annealing"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "b6beafa8937f3670a81552fd754234e8039bdc412934ea5e4a03a662fc9fe865",
"md5": "db07a40ac26cfc8d22c7334a5cf1bcd2",
"sha256": "9c9b77e1eb6b1d29b2ab741c0cbf4b6f70871e0c7df8f6a81baf62b410ea9dad"
},
"downloads": -1,
"filename": "quboassist-0.0.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "db07a40ac26cfc8d22c7334a5cf1bcd2",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 8916,
"upload_time": "2024-09-29T13:05:40",
"upload_time_iso_8601": "2024-09-29T13:05:40.135636Z",
"url": "https://files.pythonhosted.org/packages/b6/be/afa8937f3670a81552fd754234e8039bdc412934ea5e4a03a662fc9fe865/quboassist-0.0.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "bdec1524199e7e9f8cec49fd2c0468b95d0087bd3d887231de7a314eff2113a6",
"md5": "ef1ff52574158996dc017ed9fc504dd7",
"sha256": "428e22cf1660067909a752e0784534193b8dcbfb53e187b1782ae48fe3946829"
},
"downloads": -1,
"filename": "quboassist-0.0.1.tar.gz",
"has_sig": false,
"md5_digest": "ef1ff52574158996dc017ed9fc504dd7",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 11118,
"upload_time": "2024-09-29T13:05:42",
"upload_time_iso_8601": "2024-09-29T13:05:42.064954Z",
"url": "https://files.pythonhosted.org/packages/bd/ec/1524199e7e9f8cec49fd2c0468b95d0087bd3d887231de7a314eff2113a6/quboassist-0.0.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-09-29 13:05:42",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "enomotokan",
"github_project": "quboassist",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"requirements": [],
"lcname": "quboassist"
}
