.. image:: https://img.shields.io/pypi/v/penaltymodel.svg
:target: https://pypi.python.org/pypi/penaltymodel
.. image:: https://img.shields.io/pypi/pyversions/penaltymodel.svg
:target: https://pypi.python.org/pypi/penaltymodel
.. image:: https://codecov.io/gh/dwavesystems/penaltymodel/branch/master/graph/badge.svg
:target: https://codecov.io/gh/dwavesystems/penaltymodel
.. image:: https://ci.appveyor.com/api/projects/status/cqfk8il1e4hgg7ih?svg=true
:target: https://ci.appveyor.com/project/dwave-adtt/penaltymodel
.. image:: https://circleci.com/gh/dwavesystems/penaltymodel.svg?style=svg
:target: https://circleci.com/gh/dwavesystems/penaltymodel
penaltymodel
============
.. index-start-marker
One approach to solve a constraint satisfaction problem (`CSP <https://en.wikipedia.org/wiki/Constraint_satisfaction_problem>`_) using an `Ising model <https://en.wikipedia.org/wiki/Ising_model>`_ or a `QUBO <https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization>`_, is to map each individual constraint in the CSP to a 'small' Ising model or QUBO. This mapping is called a *penalty model*.
Imagine that we want to map an AND clause to a QUBO. In other words, we want the solutions
to the QUBO (the solutions that minimize the energy) to be exactly the valid configurations
of an AND gate. Let ``z = AND(x_1, x_2)``.
Before anything else, let's import that package we will need.
.. code-block:: python
import penaltymodel as pm
import dimod
import networkx as nx
Next, we need to determine the feasible configurations that we wish to target (by making the energy of these configuration in the binary quadratic low).
Below is the truth table representing an AND clause.
.. table:: AND Gate
:name: tbl_ANDgate
==================== ==================== ==================
``x_1`` ``x_2`` ``z``
==================== ==================== ==================
0 0 0
0 1 0
1 0 0
1 1 1
==================== ==================== ==================
The rows of the truth table are exactly the feasible configurations.
.. code-block:: python
feasible_configurations = [{'x1': 0, 'x2': 0, 'z': 0},
{'x1': 1, 'x2': 0, 'z': 0},
{'x1': 0, 'x2': 1, 'z': 0},
{'x1': 1, 'x2': 1, 'z': 1}]
At this point, we can get a penalty model
.. code-block:: python
bqm, gap = pm.get_penalty_model(feasible_configurations)
However, if we know the QUBO, we can build the penalty model ourselves. We observe that for the equation:
.. code-block::
E(x_1, x_2, z) = x_1 x_2 - 2(x_1 + x_2) z + 3 z + 0
We get the following energies for each row in our truth table.
.. image:: https://user-images.githubusercontent.com/8395238/34234533-8da5a364-e5a0-11e7-9d9f-068b4ab3a0fd.png
:target: https://user-images.githubusercontent.com/8395238/34234533-8da5a364-e5a0-11e7-9d9f-068b4ab3a0fd.png
We can see that the energy is minimized on exactly the desired feasible configurations. So we encode this energy function as a QUBO. We make the offset 0.0 because there is no constant energy offset.
.. code-block:: python
qubo = dimod.BinaryQuadraticModel({'x1': 0., 'x2': 0., 'z': 3.},
{('x1', 'x2'): 1., ('x1', 'z'): 2., ('x2', 'z'): 2.},
0.0,
dimod.BINARY)
We know from the table that our ground energy is ``0``, but we can calculate it using the qubo to check that this is true for the feasible configuration ``(0, 1, 0)``.
.. code-block:: python
ground_energy = qubo.energy({'x1': 0, 'x2': 1, 'z': 0})
The last value that we need is the classical gap. This is the difference in energy between the lowest infeasible state and the ground state.
.. image:: https://user-images.githubusercontent.com/8395238/34234545-9c93e5f2-e5a0-11e7-8792-5777a5c4303e.png
:target: https://user-images.githubusercontent.com/8395238/34234545-9c93e5f2-e5a0-11e7-8792-5777a5c4303e.png
With all of the pieces, we can now build the penalty model.
.. code-block:: python
classical_gap = 1
p_model = pm.PenaltyModel.from_specification(spec, qubo, classical_gap, ground_energy)
.. index-end-marker
Installation
------------
.. installation-start-marker
To install the core package:
.. code-block:: bash
pip install penaltymodel
.. installation-end-marker
License
-------
Released under the Apache License 2.0
Contributing
------------
Ocean's `contributing guide <https://docs.ocean.dwavesys.com/en/stable/contributing.html>`_
has guidelines for contributing to Ocean packages.
Release Notes
~~~~~~~~~~~~~
penaltymodel makes use of `reno <https://docs.openstack.org/reno/>`_ to manage its
release notes.
When making a contribution to penaltymodel that will affect users, create a new
release note file by running
.. code-block:: bash
reno new your-short-descriptor-here
You can then edit the file created under ``releasenotes/notes/``.
Remove any sections not relevant to your changes.
Commit the file along with your changes.
See reno's `user guide <https://docs.openstack.org/reno/latest/user/usage.html>`_
for details.
Raw data
{
"_id": null,
"home_page": "https://github.com/dwavesystems/penaltymodel",
"name": "penaltymodel",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.8",
"maintainer_email": "",
"keywords": "",
"author": "D-Wave Systems Inc.",
"author_email": "tools@dwavesys.com",
"download_url": "https://files.pythonhosted.org/packages/85/43/155f2eaac2e4f673c1af2fa9cb90857dcaa36b05cee731de2c86a2fbf53e/penaltymodel-1.1.0.tar.gz",
"platform": null,
"description": ".. image:: https://img.shields.io/pypi/v/penaltymodel.svg\n :target: https://pypi.python.org/pypi/penaltymodel\n\n.. image:: https://img.shields.io/pypi/pyversions/penaltymodel.svg\n :target: https://pypi.python.org/pypi/penaltymodel\n\n.. image:: https://codecov.io/gh/dwavesystems/penaltymodel/branch/master/graph/badge.svg\n :target: https://codecov.io/gh/dwavesystems/penaltymodel\n\n.. image:: https://ci.appveyor.com/api/projects/status/cqfk8il1e4hgg7ih?svg=true\n :target: https://ci.appveyor.com/project/dwave-adtt/penaltymodel\n\n.. image:: https://circleci.com/gh/dwavesystems/penaltymodel.svg?style=svg\n :target: https://circleci.com/gh/dwavesystems/penaltymodel\n\npenaltymodel\n============\n\n.. index-start-marker\n\nOne approach to solve a constraint satisfaction problem (`CSP <https://en.wikipedia.org/wiki/Constraint_satisfaction_problem>`_) using an `Ising model <https://en.wikipedia.org/wiki/Ising_model>`_ or a `QUBO <https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization>`_, is to map each individual constraint in the CSP to a 'small' Ising model or QUBO. This mapping is called a *penalty model*.\n\nImagine that we want to map an AND clause to a QUBO. In other words, we want the solutions\nto the QUBO (the solutions that minimize the energy) to be exactly the valid configurations\nof an AND gate. Let ``z = AND(x_1, x_2)``.\n\nBefore anything else, let's import that package we will need.\n\n.. code-block:: python\n\n import penaltymodel as pm\n import dimod\n import networkx as nx\n\nNext, we need to determine the feasible configurations that we wish to target (by making the energy of these configuration in the binary quadratic low).\nBelow is the truth table representing an AND clause.\n\n.. table:: AND Gate\n :name: tbl_ANDgate\n\n ==================== ==================== ==================\n ``x_1`` ``x_2`` ``z``\n ==================== ==================== ==================\n 0 0 0\n 0 1 0\n 1 0 0\n 1 1 1\n ==================== ==================== ==================\n\nThe rows of the truth table are exactly the feasible configurations.\n\n.. code-block:: python\n\n feasible_configurations = [{'x1': 0, 'x2': 0, 'z': 0},\n {'x1': 1, 'x2': 0, 'z': 0},\n {'x1': 0, 'x2': 1, 'z': 0},\n {'x1': 1, 'x2': 1, 'z': 1}]\n\nAt this point, we can get a penalty model\n\n.. code-block:: python\n\n bqm, gap = pm.get_penalty_model(feasible_configurations)\n\nHowever, if we know the QUBO, we can build the penalty model ourselves. We observe that for the equation:\n\n.. code-block::\n\n E(x_1, x_2, z) = x_1 x_2 - 2(x_1 + x_2) z + 3 z + 0\n\nWe get the following energies for each row in our truth table.\n\n.. image:: https://user-images.githubusercontent.com/8395238/34234533-8da5a364-e5a0-11e7-9d9f-068b4ab3a0fd.png\n :target: https://user-images.githubusercontent.com/8395238/34234533-8da5a364-e5a0-11e7-9d9f-068b4ab3a0fd.png\n\nWe can see that the energy is minimized on exactly the desired feasible configurations. So we encode this energy function as a QUBO. We make the offset 0.0 because there is no constant energy offset.\n\n.. code-block:: python\n\n qubo = dimod.BinaryQuadraticModel({'x1': 0., 'x2': 0., 'z': 3.},\n {('x1', 'x2'): 1., ('x1', 'z'): 2., ('x2', 'z'): 2.},\n 0.0,\n dimod.BINARY)\n\nWe know from the table that our ground energy is ``0``, but we can calculate it using the qubo to check that this is true for the feasible configuration ``(0, 1, 0)``.\n\n.. code-block:: python\n\n ground_energy = qubo.energy({'x1': 0, 'x2': 1, 'z': 0})\n\nThe last value that we need is the classical gap. This is the difference in energy between the lowest infeasible state and the ground state.\n\n.. image:: https://user-images.githubusercontent.com/8395238/34234545-9c93e5f2-e5a0-11e7-8792-5777a5c4303e.png\n :target: https://user-images.githubusercontent.com/8395238/34234545-9c93e5f2-e5a0-11e7-8792-5777a5c4303e.png\n\nWith all of the pieces, we can now build the penalty model.\n\n.. code-block:: python\n\n classical_gap = 1\n p_model = pm.PenaltyModel.from_specification(spec, qubo, classical_gap, ground_energy)\n\n.. index-end-marker\n\nInstallation\n------------\n\n.. installation-start-marker\n\nTo install the core package:\n\n.. code-block:: bash\n\n pip install penaltymodel\n\n.. installation-end-marker\n\nLicense\n-------\n\nReleased under the Apache License 2.0\n\nContributing\n------------\n\nOcean's `contributing guide <https://docs.ocean.dwavesys.com/en/stable/contributing.html>`_\nhas guidelines for contributing to Ocean packages.\n\nRelease Notes\n~~~~~~~~~~~~~\n\npenaltymodel makes use of `reno <https://docs.openstack.org/reno/>`_ to manage its\nrelease notes.\n\nWhen making a contribution to penaltymodel that will affect users, create a new\nrelease note file by running\n\n.. code-block:: bash\n\n reno new your-short-descriptor-here\n\nYou can then edit the file created under ``releasenotes/notes/``.\nRemove any sections not relevant to your changes.\nCommit the file along with your changes.\n\nSee reno's `user guide <https://docs.openstack.org/reno/latest/user/usage.html>`_\nfor details.\n",
"bugtrack_url": null,
"license": "Apache 2.0",
"summary": "Package for creating penalty models.",
"version": "1.1.0",
"project_urls": {
"Changes": "https://github.com/dwavesystems/penaltymodel/releases",
"Documentation": "https://docs.ocean.dwavesys.com",
"Homepage": "https://github.com/dwavesystems/penaltymodel",
"Souce Code": "https://github.com/dwavesystems/penaltymodel"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c190f884f081a5cc67221b11f8859b433e98bd71a61990a859bcc2c1db237979",
"md5": "c67b628798e66e17719e870ca7bc8431",
"sha256": "f6a5f171a71d14ee1e58c8bbc70adc6575dd56b9ce284d322aa2f4b7345a42a8"
},
"downloads": -1,
"filename": "penaltymodel-1.1.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "c67b628798e66e17719e870ca7bc8431",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.8",
"size": 36886,
"upload_time": "2024-01-16T01:11:53",
"upload_time_iso_8601": "2024-01-16T01:11:53.229671Z",
"url": "https://files.pythonhosted.org/packages/c1/90/f884f081a5cc67221b11f8859b433e98bd71a61990a859bcc2c1db237979/penaltymodel-1.1.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "8543155f2eaac2e4f673c1af2fa9cb90857dcaa36b05cee731de2c86a2fbf53e",
"md5": "fe8d88552bdb8951a80d84ba960b7e77",
"sha256": "471592e0756a6ca04c3343cb9c2aa525aaaedc42255201826c8ecdd45f592b1e"
},
"downloads": -1,
"filename": "penaltymodel-1.1.0.tar.gz",
"has_sig": false,
"md5_digest": "fe8d88552bdb8951a80d84ba960b7e77",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.8",
"size": 33800,
"upload_time": "2024-01-16T01:11:55",
"upload_time_iso_8601": "2024-01-16T01:11:55.380505Z",
"url": "https://files.pythonhosted.org/packages/85/43/155f2eaac2e4f673c1af2fa9cb90857dcaa36b05cee731de2c86a2fbf53e/penaltymodel-1.1.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-01-16 01:11:55",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "dwavesystems",
"github_project": "penaltymodel",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"circle": true,
"requirements": [],
"lcname": "penaltymodel"
}
JSON
