forked from dwavesystems/dwavebinarycsp
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathreduction.py
More file actions
96 lines (73 loc) · 4.34 KB
/
reduction.py
File metadata and controls
96 lines (73 loc) · 4.34 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# Copyright 2018 D-Wave Systems Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#
# ================================================================================================
"""
Constraints can sometimes be reduced into several smaller constraints.
"""
import itertools
from collections import defaultdict
def irreducible_components(constraint):
"""Determine the sets of variables that are irreducible.
Let V(C) denote the variables of constraint C. For a configuration x, let x|A denote the
restriction of the configuration to the variables of A. Constraint C is reducible if there
is a partition of V(C) into nonempty subsets A and B, and two constraints C_A and C_B, with
V(C_A) = A and C_B V(C_B) = B, such that a configuration x is feasible in C if and only if x|A
is feasible in C_A and x|B is feasible in C_B. A constraint is irreducible if it is not
reducible.
Args:
constraint (:obj:`.Constraint`):
Constraint to attempt to reduce.
Returns:
list[tuple]: List of tuples in which each tuple is a set of variables that is irreducible.
Examples:
This example reduces a constraint, created by specifying its valid configurations, to two
constraints. The original constraint, that valid configurations for a,b,c are 0,0,1 and
1,1,1, can be represented by two reduced constraints, for example, (c=1) & (a=b). For
comparison, an attempt to reduce a constraint representing an AND gate fails to find a
valid reduction.
>>> import dwavebinarycsp
>>> const = dwavebinarycsp.Constraint.from_configurations([(0, 0, 1), (1, 1, 1)],
... ['a', 'b', 'c'], dwavebinarycsp.BINARY)
>>> dwavebinarycsp.irreducible_components(const)
[('c',), ('a', 'b')]
>>> const_and = dwavebinarycsp.Constraint.from_configurations([(0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 1)],
... ['a', 'b', 'c'], dwavebinarycsp.BINARY)
>>> dwavebinarycsp.irreducible_components(const_and)
[('a', 'b', 'c')]
"""
# developer note: we could calculate the correlation on the variables and thereby reduce the
# number of subsets we need to check in the next step.
return _irreducible_components(constraint.configurations, constraint.variables)
def _irreducible_components(configurations, variables):
num_variables = len(variables)
# if len(configurations) <= 1:
# # if there is only one configuration then it is irreducible
# return [variables]
# for every not-trivial subset (and it's complement), check if the contraint
# is composed of the product of complement and subset
# subset and complement are defined over the indices in the configurations for simplicity
for i in range(1, num_variables // 2 + 1):
for subset in itertools.combinations(range(num_variables), i):
complement = tuple(v for v in range(num_variables) if v not in subset)
# by using sets we only keep the unique configurations
subset_configurations = {tuple(config[v] for v in subset) for config in configurations}
complement_configurations = {tuple(config[v] for v in complement) for config in configurations}
if len(configurations) == len(subset_configurations) * len(complement_configurations):
subset_variables = tuple(variables[v] for v in subset)
complement_variables = tuple(variables[v] for v in complement)
subset_components = _irreducible_components(subset_configurations, subset_variables)
complement_components = _irreducible_components(complement_configurations, complement_variables)
return subset_components + complement_components
return [variables]