{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 3-PyQUBO with OpenJij" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/OpenJij/OpenJijTutorial/blob/master/source/en/003-PyQUBO_2_OpenJij.ipynb)" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "In this chapter, we explain how to convert the cost function to QUBO with PyQUBO, Simulated Annealing, and pass variables to OpenJij. Let us show you \"Creek Coverage Problem\" as an example." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We install `pyqubo` with the following command using `pip` " ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "!pip install pyqubo" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Formulation of QUBO with PyQUBO\n", "\n", "PyQUBO is a intuitive library for fomulating QUBO & Ising models. In the previous chapters, we have shown the case withou PyQUBO. In the previous chapters, we had to formulate QUBO, then expand the expressions ourselves and put them into the Python script. However, we can eliminate that hassles with PyQUBO.\n", "\n", "PyQUBO is a handy library that can help us reduce the computational and implementation errors in our QUBO and Ising model transformations.\n", "\n", "Let us use PyQUBO as as example for the Creek Coverage Problem.\n", "\n", "For more details of this problem, see also [here (T-Wave: creek coverage problem (only Japanese))](https://qard.is.tohoku.ac.jp/T-Wave/?p=434)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We introduce the formulation of the creek coverage problem in QUBO representation.\n", "\n", "This problem is whethre the graph $G=(V, E)$ can be covered by $n$ creeks.\n", "\n", "It can be expressed in QUBO as follows.\n", "\n", "$$H = A\\sum_v \\left(1-\\sum^n_{i=1} x_{v, i}\\right)^2 \n", "+ B \\sum^n_{i=1}\\left[\n", "\\frac{1}{2}\\left(-1+\\sum_{v \\in V} x_{v,i}\\right)\\sum_{v \\in V} x_{v, i} \n", "- \\sum_{(u, v)\\in E} x_{u,i} x_{v, i}\\right]$$\n", "\n", "\n", "First term is constraint where only one color is painted on each vertex. Second shows how close the split subgraph is to creek (complete graph). Both term must be zero. However, we treat the first term as a penalty term, and second as a cost(objective function).\n", "\n", "Let us represent this QUBO using PyQUBO." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We give the Graph and the number of creek $n$ as follows in this time." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# set the number of vertex\n", "N_VER = 8\n", "# set the number of colors\n", "N_COLOR = 4\n", "# set the graph. define them which vertices are connected to each other\n", "graph = [(0,1), (0,2), (1,2), (5,6), (2,3), (2,5), (3,4), (5,7), (7, 6)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Formulation with PyQUBO\n", "\n", "We import the required classes from PyQUBO." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "from pyqubo import Array, Constraint, solve_qubo" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "At First, we prepare variables for representing QUBO. We set an array of variables using `Array`.\n", "In this time, we need the number of (N_VER) x (N_COLOR), therefore we set `shape` argument as follows." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "x = Array.create('x', shape=(N_VER,N_COLOR), vartype='BINARY')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We could create binary variable 'x' with N_VER rows and N_COLOR columns. \n", "Next, we set QUBO. PyQUBO allows us to follow the formula." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "# define first term (constraint)\n", "H_A = Constraint(sum((1-sum(x[v,i] for i in range(1,N_COLOR)))**2 for v in range(N_VER)), label='HA')\n", "# define seconde term (cost, objective function)\n", "H_B = sum((-1+sum(x[v,i] for v in range (N_VER)))/2*(sum(x[v,i] for v in range (N_VER))) - sum(x[u,i]*x[v,i] for (u,v) in graph) for i in range (1,N_COLOR))\n", "# set the entire Hamiltonian\n", "Q = H_A+H_B" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can use `Constraint` function in the first term to make the script recognize that \"this term is constraint\".\n", "The cost function is easily converted to QUBO (Python dictionary type) with `Q.compile().to_qubo()`.\n", "\n", "In OpenJij and D-Wave Ocean, QUBO is assumed to be represented by a Python dictionary type.\n", "\n", "We can run it on each solver by `.compile`." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "# compile this model\n", "model = Q.compile()\n", "qubo, offset = model.to_qubo()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`qubo` is set to QUBO and `offset` is set to the constant that appears when it is converted to QUBO.\n", "\n", "A Simulated Annealing solver `solve_qubo(qubo)` in PyQUBO is now deprecated. It is recommended to call D-Wave Ocean SDK `dwave-neal` directly." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " x[0][1] x[0][2] x[0][3] x[1][1] x[1][2] x[1][3] ... x[7][3] energy num_oc.\n", "0 0 0 1 0 0 1 ... 0 -8.0 1\n", "['BINARY', 1 rows, 1 samples, 24 variables]\n" ] } ], "source": [ "# use SA on neal\n", "import neal\n", "sampler = neal.SimulatedAnnealingSampler()\n", "raw_solution = sampler.sample_qubo(qubo)\n", "print(raw_solution)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "`.first.sample` extracts the lowest energy of all derived solutions." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'x[0][1]': 0,\n", " 'x[0][2]': 0,\n", " 'x[0][3]': 1,\n", " 'x[1][1]': 0,\n", " 'x[1][2]': 0,\n", " 'x[1][3]': 1,\n", " 'x[2][1]': 0,\n", " 'x[2][2]': 0,\n", " 'x[2][3]': 1,\n", " 'x[3][1]': 1,\n", " 'x[3][2]': 0,\n", " 'x[3][3]': 0,\n", " 'x[4][1]': 1,\n", " 'x[4][2]': 0,\n", " 'x[4][3]': 0,\n", " 'x[5][1]': 0,\n", " 'x[5][2]': 1,\n", " 'x[5][3]': 0,\n", " 'x[6][1]': 0,\n", " 'x[6][2]': 1,\n", " 'x[6][3]': 0,\n", " 'x[7][1]': 0,\n", " 'x[7][2]': 1,\n", " 'x[7][3]': 0}" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "raw_solution.first.sample" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's look at the solutions obtained. We can see that is is stored in a dictionary type with the string as the key like 'x[0][0]': 1.\n", "\n", "In this form, it is difficult to analyze from now on. \n", "\n", "PyQUBO has the `.decode_sample()` function to convert it into a more manageable form." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{0: {1: 0, 2: 0, 3: 1},\n", " 1: {1: 0, 2: 0, 3: 1},\n", " 2: {1: 0, 2: 0, 3: 1},\n", " 3: {1: 1, 2: 0, 3: 0},\n", " 4: {1: 1, 2: 0, 3: 0},\n", " 5: {1: 0, 2: 1, 3: 0},\n", " 6: {1: 0, 2: 1, 3: 0},\n", " 7: {1: 0, 2: 1, 3: 0}}" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# decode (convert) result into a manageable form\n", "decoded_sample = model.decode_sample(raw_solution.first.sample, vartype=\"BINARY\")\n", "# below is for visualization\n", "# .array(variable, index) extracts the specific element of the index\n", "x_solution = {}\n", "for i in range(N_VER):\n", " x_solution[i] = {}\n", " for j in range(1,N_COLOR):\n", " x_solution[i][j] = decoded_sample.array('x', (i, j))\n", "x_solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can see three groups, (0,1,2), (3, 4), (5,6,7).\n", "\n", "This solution forms creeks on each of the graphs given this time.\n", "\n", "`.constraints(only_broken=True)` shows how the penalty term is broken (when penalty is not equal to 0)." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{}\n" ] } ], "source": [ "print(decoded_sample.constraints(only_broken=True))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "In this time, We can see empty dictionary because constraint is satisfied.\n", "\n", "`decode` function is very useful that can automatically check the constraints is satisfied or not." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Run with OpenJij\n", "\n", "We just solved creek coverage problem in PyQUBO SA. Next, let's use OpenJij.\n", "\n", "Similarly, OpenJij can perform SA, but we use SQA, which is not implemented in PyQUBO." ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "# import OpenJij\n", "import openjij as oj\n", "\n", "# solve this problem with SQA\n", "sampler = oj.SQASampler()\n", "# substitute into QUBO what we created using .to_qubo\n", "response = sampler.sample_qubo(Q=qubo)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can run with other algorithms and machines by replaceing `sampler` part.\n", "\n", "\n", "Finally, we decode the result with OpenJij using PyQUBO decoder.\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{0: {1: 0, 2: 0, 3: 1},\n", " 1: {1: 0, 2: 0, 3: 1},\n", " 2: {1: 0, 2: 0, 3: 1},\n", " 3: {1: 1, 2: 0, 3: 0},\n", " 4: {1: 1, 2: 0, 3: 0},\n", " 5: {1: 0, 2: 1, 3: 0},\n", " 6: {1: 0, 2: 1, 3: 0},\n", " 7: {1: 0, 2: 1, 3: 0}}" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# get the state of lowest energy\n", "dict_solution = response.first.sample\n", "# decode\n", "decoded_sample = model.decode_sample(raw_solution.first.sample, vartype=\"BINARY\")\n", "# visualize\n", "# .array(variable, index) extracts the specific element\n", "x_solution = {}\n", "for i in range(N_VER):\n", " x_solution[i] = {}\n", " for j in range(1,N_COLOR):\n", " x_solution[i][j] = decoded_sample.array('x', (i, j))\n", "x_solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Conclusion\n", "\n", "We learned how to formulate it using PyQUBO and how it works with OpenJij.\n", "\n", "Procedures are as follows.\n", "\n", "1. set up variables in pyqubo.Array\n", "2. formulate QUBO\n", "3. compile QUBO and convert it to a dictionary type\n", "4. solve optimization problems using solvers such as OpenJij that accepts dictionary type QUBOs.\n", "5. decode solution as a dictionary with the subscript as a key.\n", "\n", "PyQUBO is useful and powerful tool for formulationg and evaluating constraints. When we use in conjunction with OpenJij, which provides a variety of solvers, it provides comfortable development experience." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Reference:PyQUBO official document\n", "https://pyqubo.readthedocs.io/en/latest/reference/array.html?highlight=arry%20create" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.3" } }, "nbformat": 4, "nbformat_minor": 2 }