OR-Tools  8.2
symmetry_util.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
17
18namespace operations_research {
19namespace sat {
20
21std::vector<std::vector<int>> BasicOrbitopeExtraction(
22 const std::vector<std::unique_ptr<SparsePermutation>>& generators) {
23 // Count the number of permutations that are compositions of 2-cycle and
24 // regroup them according to the number of cycles.
25 std::vector<std::vector<int>> num_cycles_to_2cyclers;
26 for (int g = 0; g < generators.size(); ++g) {
27 const std::unique_ptr<SparsePermutation>& perm = generators[g];
28 bool contain_only_2cycles = true;
29 const int num_cycles = perm->NumCycles();
30 for (int i = 0; i < num_cycles; ++i) {
31 if (perm->Cycle(i).size() != 2) {
32 contain_only_2cycles = false;
33 break;
34 }
35 }
36 if (!contain_only_2cycles) continue;
37 if (num_cycles >= num_cycles_to_2cyclers.size()) {
38 num_cycles_to_2cyclers.resize(num_cycles + 1);
39 }
40 num_cycles_to_2cyclers[num_cycles].push_back(g);
41 }
42
43 // Heuristic: we try to grow the orbitope that has the most potential for
44 // fixing variables.
45 //
46 // TODO(user): We could grow each and keep the real maximum.
47 int best = -1;
48 int best_score = 0;
49 for (int i = 0; i < num_cycles_to_2cyclers.size(); ++i) {
50 if (num_cycles_to_2cyclers[i].size() > 1) {
51 const int num_perms = num_cycles_to_2cyclers[i].size() + 1;
52 VLOG(1) << "Potential orbitope: " << i << " x " << num_perms;
53 const int64 score = std::min(i, num_perms);
54 if (score > best_score) {
55 best = i;
56 best_score = score;
57 }
58 }
59 }
60
61 std::vector<std::vector<int>> orbitope;
62 if (best == -1) return orbitope;
63
64 // We will track the element already added so we never have duplicates.
65 std::vector<bool> in_matrix;
66
67 // Greedily grow the orbitope.
68 orbitope.resize(best);
69 for (const int g : num_cycles_to_2cyclers[best]) {
70 // Start using the first permutation.
71 if (orbitope[0].empty()) {
72 const std::unique_ptr<SparsePermutation>& perm = generators[g];
73 const int num_cycles = perm->NumCycles();
74 for (int i = 0; i < num_cycles; ++i) {
75 for (const int x : perm->Cycle(i)) {
76 orbitope[i].push_back(x);
77 if (x >= in_matrix.size()) in_matrix.resize(x + 1, false);
78 in_matrix[x] = true;
79 }
80 }
81 continue;
82 }
83
84 // We want to find a column such that g sends it to variables not already
85 // in the orbitope matrix.
86 //
87 // Note(user): This relies on the cycle in each permutation to be ordered by
88 // smaller element first. This way we don't have to account any row
89 // permutation of the orbitope matrix. The code that detect the symmetries
90 // of the problem should already return permutation in this canonical
91 // format.
92 std::vector<int> grow;
93 int matching_column_index = -1;
94 const std::unique_ptr<SparsePermutation>& perm = generators[g];
95 const int num_cycles = perm->NumCycles();
96 for (int i = 0; i < num_cycles; ++i) {
97 // Extract the two elements of this transposition.
98 std::vector<int> tmp;
99 for (const int x : perm->Cycle(i)) tmp.push_back(x);
100 const int a = tmp[0];
101 const int b = tmp[1];
102
103 // We want one element to appear in matching_column_index and the other to
104 // not appear at all.
105 int num_matches_a = 0;
106 int num_matches_b = 0;
107 int last_match_index = -1;
108 for (int j = 0; j < orbitope[i].size(); ++j) {
109 if (orbitope[i][j] == a) {
110 ++num_matches_a;
111 last_match_index = j;
112 } else if (orbitope[i][j] == b) {
113 ++num_matches_b;
114 last_match_index = j;
115 }
116 }
117 if (last_match_index == -1) break;
118 if (matching_column_index == -1) {
119 matching_column_index = last_match_index;
120 }
121 if (matching_column_index != last_match_index) break;
122 if (num_matches_a == 0 && num_matches_b == 1) {
123 if (a >= in_matrix.size() || !in_matrix[a]) grow.push_back(a);
124 } else if (num_matches_a == 1 && num_matches_b == 0) {
125 if (b >= in_matrix.size() || !in_matrix[b]) grow.push_back(b);
126 } else {
127 break;
128 }
129 }
130
131 // If grow is of full size, we can extend the orbitope.
132 if (grow.size() == num_cycles) {
133 for (int i = 0; i < orbitope.size(); ++i) {
134 orbitope[i].push_back(grow[i]);
135 if (grow[i] >= in_matrix.size()) in_matrix.resize(grow[i] + 1, false);
136 in_matrix[grow[i]] = true;
137 }
138 }
139 }
140
141 return orbitope;
142}
143
144std::vector<int> GetOrbits(
145 int n, const std::vector<std::unique_ptr<SparsePermutation>>& generators) {
146 MergingPartition union_find;
147 union_find.Reset(n);
148 for (const std::unique_ptr<SparsePermutation>& perm : generators) {
149 const int num_cycles = perm->NumCycles();
150 for (int i = 0; i < num_cycles; ++i) {
151 // Note that there is currently no random access api like cycle[j].
152 int first;
153 bool is_first = true;
154 for (const int x : perm->Cycle(i)) {
155 if (is_first) {
156 first = x;
157 is_first = false;
158 } else {
159 union_find.MergePartsOf(first, x);
160 }
161 }
162 }
163 }
164
165 int num_parts = 0;
166 std::vector<int> orbits(n, -1);
167 for (int i = 0; i < n; ++i) {
168 if (union_find.NumNodesInSamePartAs(i) == 1) continue;
169 const int root = union_find.GetRootAndCompressPath(i);
170 if (orbits[root] == -1) orbits[root] = num_parts++;
171 orbits[i] = orbits[root];
172 }
173 return orbits;
174}
175
176std::vector<int> GetOrbitopeOrbits(
177 int n, const std::vector<std::vector<int>>& orbitope) {
178 std::vector<int> orbits(n, -1);
179 for (int i = 0; i < orbitope.size(); ++i) {
180 for (int j = 0; j < orbitope[i].size(); ++j) {
181 CHECK_EQ(orbits[orbitope[i][j]], -1);
182 orbits[orbitope[i][j]] = i;
183 }
184 }
185 return orbits;
186}
187
188} // namespace sat
189} // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define VLOG(verboselevel)
Definition: base/logging.h:978
int MergePartsOf(int node1, int node2)
int64_t int64
std::vector< int > GetOrbitopeOrbits(int n, const std::vector< std::vector< int > > &orbitope)
std::vector< int > GetOrbits(int n, const std::vector< std::unique_ptr< SparsePermutation > > &generators)
std::vector< std::vector< int > > BasicOrbitopeExtraction(const std::vector< std::unique_ptr< SparsePermutation > > &generators)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...