Included Classes

PenaltyModel

class PenaltyModel(graph, decision_variables, feasible_configurations, vartype, model, classical_gap, ground_energy, ising_linear_ranges=None, ising_quadratic_ranges=None)[source]

Container class for the components that make up a penalty model.

A penalty model is a small Ising problem or QUBO that has ground states that match the feasible configurations and excited states that have a classical energy greater than the ground energy by at least the classical gap.

PenaltyModel is a subclass of Specification.

Parameters:
  • graph (networkx.Graph/iterable[edge]) – Defines the structure of the desired binary quadratic model. Each node in the graph represents a variable and each edge defines an interaction between two variables. If given as an iterable of edges, the graph will be constructed by adding each edge to an (initially) empty graph.
  • decision_variables (iterable) – The labels of the penalty model’s decision variables. Each variable label in decision_variables must correspond to a node in graph. Should be an ordered iterable of hashable labels.
  • feasible_configurations (dict[tuple[int], number]/iterable[tuple[int]]) – The set of feasible configurations. Defines the allowed configurations of the decision variables allowed by the constraint. Each feasible configuration should be a tuple, each element of which must be of a value matching vartype. If given as a dict, the key is the feasible configuration and the value is the desired relative energy. If given as an iterable, it will be case to a dict where the relative energies are all 0.
  • vartype (Vartype/str/set) – The variable type desired for the penalty model. Accepted input values: Vartype.SPIN, 'SPIN', {-1, 1} Vartype.BINARY, 'BINARY', {0, 1}
  • model (dimod.BinaryQuadraticModel) – A binary quadratic model that has ground states that match the feasible_configurations.
  • classical_gap (numeric) – The difference in classical energy between the ground state and the first excited state. Must be positive.
  • ground_energy (numeric) – The minimum energy of all possible configurations.
  • ising_linear_ranges (dict[node, [number, number]], optional, default=None) – When the penalty model is spin-valued, specifies the allowed range for each of the linear biases. If a dict, should be of the form {v: [min, max], …} where v is a variable in the desired penalty model and (min, max) defines the acceptable range for the linear bias associated with v. If None, the default will be set to {v: [-1, 1], …} for each v in graph. A partial assignment is allowed.
  • ising_quadratic_ranges (dict[node, dict[node, [number, number]], optional, default=None) – When the penalty model is spin-valued, specifies the allowed range for each of the quadratic biases. If a dict, should be of the form {v: {u: [min, max], …}, …} where u and v are variables in the desired penalty model and u, v have an interaction - there is an edge between nodes u, v in graph. (min, max) the acceptable range for the quadratic bias associated with u, v. If None, the default will be set to {v: {u: [min, max], …}, u: {v: [min, max], …}, …} for each edge u, v in graph. A partial assignment is allowed.

Examples

The penalty model can be created from its component parts:

>>> import networkx as nx
>>> import dimod
>>> graph = nx.path_graph(3)
>>> decision_variables = (0, 2)  # the ends of the path
>>> feasible_configurations = {(-1, -1), (1, 1)}  # we want the ends of the path to agree
>>> model = dimod.BinaryQuadraticModel({0: 0, 1: 0, 2: 0}, {(0, 1): -1, (1, 2): -1}, 0.0, dimod.SPIN)
>>> classical_gap = 2.0
>>> ground_energy = -2.0
>>> widget = pm.PenaltyModel(graph, decision_variables, feasible_configurations, dimod.SPIN,
...                          model, classical_gap, ground_energy)

Or it can be created from a specification:

>>> spec = pm.Specification(graph, decision_variables, feasible_configurations, dimod.SPIN)
>>> widget = pm.PenaltyModel.from_specification(spec, model, classical_gap, ground_energy)
decision_variables

Maps the feasible configurations to the graph.

Type:tuple
classical_gap

The difference in classical energy between the ground state and the first excited state. Must be positive.

Type:numeric
feasible_configurations

The set of feasible configurations. The value is the (relative) energy of each of the feasible configurations.

Type:dict[tuple[int], number]
graph

The graph that defines the relation between variables in the penaltymodel. The node labels will be used as the variable labels in the binary quadratic model.

Type:networkx.Graph
ground_energy

The minimum energy of all possible configurations.

Type:numeric
ising_linear_ranges

Defines the energy ranges available for the linear biases of the penalty model.

Type:dict[node, (number, number)]
model

A binary quadratic model that has ground states that match the feasible_configurations.

Type:dimod.BinaryQuadraticModel
ising_quadratic_ranges

Defines the energy ranges available for the quadratic biases of the penalty model.

Type:dict[edge, (number, number)]
vartype

The variable type.

Type:dimod.Vartype
classmethod from_specification(specification, model, classical_gap, ground_energy)[source]

Construct a PenaltyModel from a Specification.

Parameters:
  • specification (Specification) – A specification that was used to generate the model.
  • model (dimod.BinaryQuadraticModel) – A binary quadratic model that has ground states that match the feasible_configurations.
  • classical_gap (numeric) – The difference in classical energy between the ground state and the first excited state. Must be positive.
  • ground_energy (numeric) – The minimum energy of all possible configurations.
Returns:

PenaltyModel

relabel_variables(mapping, inplace=True)[source]

Relabel the variables and nodes according to the given mapping.

Parameters:
  • mapping (dict[hashable, hashable]) – A dict with the current variable labels as keys and new labels as values. A partial mapping is allowed.
  • inplace (bool, optional, default=True) – If True, the penalty model is updated in-place; otherwise, a new penalty model is returned.
Returns:

A PenaltyModel with the variables relabeled according to mapping.

Return type:

PenaltyModel

Examples

>>> spec = pm.Specification(nx.path_graph(3), (0, 2), {(-1, -1), (1, 1)}, dimod.SPIN)
>>> model = dimod.BinaryQuadraticModel({0: 0, 1: 0, 2: 0}, {(0, 1): -1, (1, 2): -1}, 0.0, dimod.SPIN)
>>> penalty_model = pm.PenaltyModel.from_specification(spec, model, 2., -2.)
>>> relabeled_penalty_model = penalty_model.relabel_variables({0: 'a'}, inplace=False)
>>> relabeled_penalty_model.decision_variables
('a', 2)
>>> spec = pm.Specification(nx.path_graph(3), (0, 2), {(-1, -1), (1, 1)}, dimod.SPIN)
>>> model = dimod.BinaryQuadraticModel({0: 0, 1: 0, 2: 0}, {(0, 1): -1, (1, 2): -1}, 0.0, dimod.SPIN)
>>> penalty_model = pm.PenaltyModel.from_specification(spec, model, 2., -2.)
>>> __ = penalty_model.relabel_variables({0: 'a'}, inplace=True)
>>> penalty_model.decision_variables
('a', 2)

Specification

class Specification(graph, decision_variables, feasible_configurations, vartype, ising_linear_ranges=None, ising_quadratic_ranges=None, min_classical_gap=2)[source]

Specification for a PenaltyModel.

See PenaltyModel documentation for a fuller description of the different components. A specification can be thought of as an incomplete penalty model.

Parameters:
  • graph (networkx.Graph/iterable[edge]) – Defines the structure of the desired binary quadratic model. Each node in the graph represents a variable and each edge defines an interaction between two variables. If given as an iterable of edges, the graph will be constructed by adding each edge to an (initially) empty graph.
  • decision_variables (iterable) – The labels of the penalty model’s decision variables. Each variable label in decision_variables must correspond to a node in graph. Should be an ordered iterable of hashable labels.
  • feasible_configurations (dict[tuple[int], number]/iterable[tuple[int]]) – The set of feasible configurations. Defines the allowed configurations of the decision variables allowed by the constraint. Each feasible configuration should be a tuple, each element of which must be of a value matching vartype. If given as a dict, the key is the feasible configuration and the value is the desired relative energy. If given as an iterable, it will be case to a dict where the relative energies are all 0.
  • vartype (dimod.Vartype/str/set) – The variable type desired for the penalty model. Accepted input values: Vartype.SPIN, 'SPIN', {-1, 1} Vartype.BINARY, 'BINARY', {0, 1}
  • ising_linear_ranges (dict[node, [number, number]], optional, default=None) – When the penalty model is spin-valued, specifies the allowed range for each of the linear biases. If a dict, should be of the form {v: [min, max], …} where v is a variable in the desired penalty model and (min, max) defines the acceptable range for the linear bias associated with v. If None, the default will be set to {v: [-1, 1], …} for each v in graph. A partial assignment is allowed.
  • ising_quadratic_ranges (dict[node, dict[node, [number, number]], optional, default=None) – When the penalty model is spin-valued, specifies the allowed range for each of the quadratic biases. If a dict, should be of the form {v: {u: [min, max], …}, …} where u and v are variables in the desired penalty model and u, v have an interaction - there is an edge between nodes u, v in graph. (min, max) the acceptable range for the quadratic bias associated with u, v. If None, the default will be set to {v: {u: [min, max], …}, u: {v: [min, max], …}, …} for each edge u, v in graph. A partial assignment is allowed.

Examples

>>> import networkx as nx
>>> import dimod
>>> graph = nx.path_graph(5)
>>> decision_variables = (0, 4)  # the ends of the path
>>> feasible_configurations = {(-1, -1), (1, 1)}  # we want the ends of the path to agree
>>> vartype = dimod.Vartype.SPIN
>>> spec = pm.Specification(graph, decision_variables, feasible_configurations, vartype)

If we want to make the interaction between (0, 1) ferromagnetic (negative):

>>> ising_quadratic_ranges = {0: {1: (-1, 0)}}
>>> spec = pm.Specification(graph, decision_variables, feasible_configurations, vartype)
decision_variables

The labels of the penalty model’s decision variables. Each variable label in decision_variables must correspond to a node in graph.

Type:tuple
feasible_configurations

The set of feasible configurations. Defines the allowed configurations of the decision variables allowed by the constraint. The key is the allowed configuration, the value is the relative energy of each configuration.

Type:dict[tuple[int], number]
graph

Defines the structure of the desired binary quadratic model. Each node in the graph represents a variable and each edge defines an interaction between two variables.

Type:networkx.Graph
ising_linear_ranges

When the penalty model is spin-valued, specifies the allowed range for each of the linear biases. A dict of the form {v: [min, max], …} where v is a variable in the desired penalty model and [min, max] defines the acceptable range for the linear bias associated with v.

Type:dict[node, [number, number], optional, default=None
ising_quadratic_ranges

When the penalty model is spin-valued, specifies the allowed range for each of the quadratic biases. A dict of the form {v: {u: [min, max], …}, u: {v: [min, max], …}, …} where u and v are variables in the desired penalty model and u, v have an interaction - there is an edge between nodes u, v in graph.

Type:dict[node, dict[node, [number, number]]], optional, default=None
min_classical_gap

This is a threshold value for the classical gap. It describes the minimum energy gap between the highest feasible state and the lowest infeasible state. Default value is 2.

Type:float
relabel_variables(mapping, inplace=True)[source]

Relabel the variables and nodes according to the given mapping.

Parameters:
  • mapping (dict) – a dict mapping the current variable/node labels to new ones.
  • inplace (bool, optional, default=True) – If True, the specification is updated in-place; otherwise, a new specification is returned.
Returns:

A Specification with the variables relabeled according to mapping. If copy=False returns itself, if copy=True returns a new Specification.

Return type:

Specification