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 
18 namespace operations_research {
19 namespace sat {
20 
21 std::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 
144 std::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 
176 std::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< std::vector< int > > BasicOrbitopeExtraction(const std::vector< std::unique_ptr< SparsePermutation >> &generators)
std::vector< int > GetOrbits(int n, const std::vector< std::unique_ptr< SparsePermutation >> &generators)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...